Binary Tree: Inorder Predecessor

Write an algorithm to find the ‘previous’ node (e.g., in-order predecessor) of a given node in a binary search tree where each node has a link to its parent.


To Find the inorder predecessor of node u:
If u has a left child, l, then pred(u) is the rightmost descendent of l
Otherwise, pred(u) is the closest ancestor, v, of u (if any) such that u is de-
scended from the right child of v.
If there is no such ancestor, then pred(u) is undefined.

The running time of TREE-SUCCESSOR on a tree of height his O(h), since we either follow a path up the tree or follow a path down the tree. The procedure TREE-PREDECESSOR, which is symmetric to TREE-SUCCESSOR, also runs in time O(h).

Taking the nodes one at a time and applying the rule:
node C: Does not have a left child. Closest ancestor such that node-C is de-
scended from the right child is node-A. Therefore, the predecessor of node-C
is node-A.
node A: Has a left child, node-B. Rightmost descendent of node-B is node-E.
node E: Has a left child, node-F. Rightmost descendent of node-F is node-G.
node G: Does not have a left child. Closest ancestor such that node-G is de-
scended from the right child is node-F.
node F: Does not have a left child. Closest ancestor such that node-F is de-
scended from the right child is node-B.
node B: Has a left child, node-D. Rightmost descendent of node-D is node-D
itself.
node D: Does not have a left child. There is no ancestor such that node-D is
descended from the right child. Therefore, the predecessor of node-D is
undefined.