Inorder successor OR Predecessor of BST node

It is important to understand inorder successor of BST because it helps us understand deletion of node from a tree, when the node deleted has 2 children.

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 descended from the left child of v. If there is no such ancestor, then succ(u) is undefined.
  

An iterator would start with the leftmost node.

For example, an inorder traversal of the following binary tree yields the sequence DBFGEAC.

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 ancestor,
v such that node-C is descended from the left child of v. However,
there is no such ancestor, so succ(C) is unde ned (node-C has no successor).

To summarize in table :

Node	Successor
A	C
B	F
C	NONE
D	B
E	A
F	G
G	E

Thanks