Make delicious recipes!

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 left-most 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;

Like us on Facebook to remain in touch
with the latest in technology and tutorials!

Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Email: (Your email is not shared with anybody)

Facebook comments:

Site Owner: Sachin Goyal