Sucessor & Predecessor Algo For Tree Traversal

successor -
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 un defi ned.
Preorder Successor
To find the preorder successor of node u:
If u has a left child, l, then succ(u) is l.
Otherwise, if u has a right child, r, then succ(u) is r.
Otherwise, u is a leaf and the following rules apply:
if u is a left child and has a right sibling, rs, then succ(u) is rs.
otherwise, if u has an ancestor, v, which is a left-child and v has a right sibling,
vrs, then succ(u) is vrs
If there is no such ancestor, then succ(u) is undefi ned.
Postorder successor
To nd the postorder successor of node u:
If u is the root of the tree, succ(u) is unde ned.
Otherwise, if u is a right child, succ(u) is parent(u).
Otherwise u is a left child and the following applies:
if u has a right sibling, r, succ(u) is the leftmost leaf in r's subtree
otherwise succ(u) is parent(u).
Predecessor
To fi nd 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 descended
from the right child of v.
If there is no such ancestor, then pred(u) is undefi ned.
Preorder Predecessor
To find the preorder predecessor of node u:
If u is the root of the tree, then pred(u) is unde fined
If u has a left sibling, ls, then pred(u) is the rightmost descendent of ls
Otherwise, pred(u) is parent(u).

Postorder Predecessor
To nd the postorder predecessor of node u:
If u has a right child, r, then pred(u) is r.
Otherwise If u has a left child, l, then pred(u) is l.
Otherwise if u has a left sibling, ls, then pred(u) is ls
Otherwise if u has an ancestor, v, which is a right child and has a left sibling,
vls, then pred(u) is vls
Otherwise, pred(u) is unde ned.
An iterator would start with the root of the tree.