EPI300 Q14.2.

I feel code is hard to write, as it’s hard to visualize or build the tree.

In-order walk must enter at root. If we only have the current node as the only input, then I assume there’s an uplink in each node. Here’s my algo:

Case 1: if i have Right child, then descend there and then descend Left all the way to a leaf node and return. Easy case.

Case 2: now we know i have no Right child. Am i a Left child? If yes then return my parent. Easy case.

Case 3: Now we know I am the Right child, without my own right child. This is the worst case. My left child (if any) is irrelevant, so effectively I am a leaf node. A right leaf node. Solution: Move up step by step. After the first up-right move, descend Left all the way.

For predecessor, I found this algo online, but it can’t move up so unable to support Case 2 and 3.

`/* Find the inorder predecessor of current */`

`pre = current->left;`

`while (pre->right != NULL && pre->right != current)`

`pre = pre->right;`

Based on that, here’s my successor algo:

`/* Find the inorder sucessor of current */`

`pre = current->right;`

`while (pre->left != NULL && pre->left != current)`

`pre = pre->left;`