BinaryTree: Inorder Successor

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

Approach:
To Find the inorder successor of node u:
If u has a right child, r, then succ(u) is the leftmost descendent of r

Otherwise, succ(u) is the closest ancestor, v, of u (if any) such that u is de-
scended from the left child of v. If there is no such ancestor, then succ(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 D: Does not have a right child. Its successor is the closest ancestor, v
such that node-D is descended from the left child of v. Node-D is descended
from the left child of node-B, so succ(D) is node-B.
node B: Has a right child (node-E), so successor is the leftmost descendent of
node-E, namely node-F.
node F: Has a right child (node-G), so successor is the leftmost descendent of
node-G, namely node-G itself.
node G: Does not have a right child. Its successor is the closest ancestor, v
such that node-G is descended from the left child of v. Node-G is descended
from the left child of node-E, so succ(G) is node-E.
node E: Does not have a right child. Its successor is the closest ancestor, v
such that node-E is descended from the left child of v. Node-E is descended
from the left child of node-A, so succ(E) is node-A.
node A: Has a right child (node-C), so successor is the leftmost descendent of
node-C, namely node-C itself.
node C: Does not have a right child. Its successor would be the closest ances-
tor, v such that node-C is descended from the left child of v. However,
there is no such ancestor, so succ(C) is undefined (node-C has no succes-
sor).

Code: