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;