#cs/cp #review #flashcards/cs
## Summary
Given a node $t$, find its in-order predecessor and successor. If either does not exist, return `None`.
## What Makes this Difficult
A target node can appear in several situations that we need to account for.
1. $t$ is the root.
```mermaid
graph TD
N4q9z0((t))
N4q9z1((1))
N4q9z2((5))
N4q9z0 --> N4q9z1
N4q9z0 --> N4q9z2
```
2. $t$ is a leaf node.
```mermaid
graph TD
Nm8zc0((3))
Nm8zc1((1))
Nm8zc2((t))
Nm8zc0 --> Nm8zc1
Nm8zc0 --> Nm8zc2
```
3. $t$ has no left child.
```mermaid
graph TD
N18x00((t))
N18x01[ ]
style N18x01 width:0px,fill:none,stroke:none
N18x02((5))
N18x00 ~~~ N18x01
N18x00 --> N18x02
```
4. $t$ has no right child.
```mermaid
graph TD
N4sil0((6))
N4sil1((2))
N4sil2((t))
N4sil3((1))
N4sil4((3))
N4sil5((7))
N4sil6[ ]
style N4sil6 width:0px,fill:none,stroke:none
N4sil0 --> N4sil1
N4sil0 --> N4sil2
N4sil1 --> N4sil3
N4sil1 --> N4sil4
N4sil2 --> N4sil5
N4sil2 ~~~ N4sil6
```
5. $t$ has two children.
```mermaid
graph TD
Nua7n0((6))
Nua7n1((2))
Nua7n2((t))
Nua7n3((1))
Nua7n4((3))
Nua7n5((7))
Nua7n6((9))
Nua7n0 --> Nua7n1
Nua7n0 --> Nua7n2
Nua7n1 --> Nua7n3
Nua7n1 --> Nua7n4
Nua7n2 --> Nua7n5
Nua7n2 --> Nua7n6
```
## How We Solve This
Predecessor and successor are symmetric operations.
To find the **successor** of $t$:
1. If $t$ has a right child, the successor is the smallest node in its right subtree: go right once, then left as far as possible.
2. Otherwise, the successor is the nearest ancestor whose left subtree contains $t$. With parent pointers, move upward while the current node is a right child. When it is a left child, its parent is the successor. If there is no such ancestor, return `None`.
To find the **predecessor** of $t$:
1. If $t$ has a left child, the predecessor is the largest node in its left subtree: go left once, then right as far as possible.
2. Otherwise, the predecessor is the nearest ancestor whose right subtree contains $t$. With parent pointers, move upward while the current node is a left child. When it is a right child, its parent is the predecessor. If there is no such ancestor, return `None`.
> [!TIP]
> Apply both algorithms to each case above. Does the answer come from one of $t