Find inorder successor in a tree if each node has parent pointer
We
need to consider the following different cases:
1)
If a node has right child, then leftmost child of this right subtree
is the successor.
2)
If no right child is there, then 2 cases occur:
a)
If current node is left child of its parent, then parent is the
successor.
b)
If current node is right child of its parent, then continue
traversing the parent till a parent is found in whose left child
current tree lies.
With
these considerations, the code can be written as:
TreeNode inorderSuccessor(TreeNode n)
{
if (n == null) return null;
if (n.right != null)
return leftMostChild(n.right);
// Go up until we are left grandchildren of some node
TreeNode p;
while (n.parent != null)
{
p = n.parent;
if (p.left == n)
return p;
n = p;
}
return null;
}
