Question

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

Solution

1. If current node have a right child, return the leftmost leaf of right child.

2. If current node have no right child:

   1. If current is parent’s left child, then return parent node.

   2. If current is parent’s right child, look all the way up until find a right-turning parent.

   3. If all parent is not right-turning. Return null.

Code

written by me

public static TreeNode inorderSucc(TreeNode e) {
    if (e == null)
        return null;
    if (e.right != null) {
        TreeNode p = e.right;
        while (p.left != null) {
            p = p.left;
        }
        return p;
    } else {
        TreeNode p = e.parent;
        while (p != null && p.right == e) {
            e = p;
            p = e.parent;
        }
        return p;
    }
}