3.4 Inorder Successor in BST

Logical Steps

1. If p has a right tree, the in order successor is at the very left node of the right tree
2. If p has no right tree, the successor is its parent or null
3. Initiate successor cursor at null (if not being used, its gonna be at null)
4. In order to not lost the position of root cursor, start looking of for parent by using binary search (since its a BST), whenever goes left, record the previous node as successor (parent)
5. Search for successor in right tree by going to right node, and go all the way to the left
6. Decide its in left tree, right tree or null

Code Template

public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
    // boundary case, if p or root is null, return null
    if (p == null || root == null)
        return null;

    /** step 1, find p from root
     * since if p is on the left tree
     * its successor is its parent
     * so for all left trees, we record its parent as successor value
     * initiate successor with null to avoid collide with first root
     */
    TreeNode successor = null;

    /** start looking for p
     * since its a BST, do binary search in BST
     * record succesor (parent) for all left trees
     * until root == null or found p in tree
     */
    while (root.val != p.val && root != null) {
        if (p.val > root.val) {
            root = root.right;
        }else{
            successor = root;
            root = root.left;
        }
    }

    /** step 2, find successor
     * if p has a right tree
     * successor is the left most node in right tree
     */
    if (p.right != null) {
        // go to right tree first
        p = p.right;

        // go all the way left from there
        while(p.left != null){
            p = p.left;
        }

        // return left most node in right tree
        return p;
    }else{
        // if p doesn't have right tree, return sucessor found in step 1
        return successor;
    }
}

Common Mistakes

1. When look for successors, initiate successor cursor at root: its will collide when root is p

    /** this is a mistake example
    * if initiate successor at root
    * when p acutally = root, it will collide
    */
    TreeNode successor = root;
    while (root.val != p.val && root != null) {
        if (p.val > root.val) {
            root = root.right;
        }else{
            successor = root;
            root = root.left;
        }
    }
   

2. Move successor cursor to root when traversing in tree to find P: parent is successor only when p is at left tree of parent, if root travels top-down to the right, it doesn't make sense to mark parent as in order succesor node

    TreeNode successor = null;
    while (root.val != p.val && root != null) {
        if (p.val > root.val) {
            /** this is a mistake example
            * when move top-down to right tree
            * parent node is not in order successor
            */
            successor = root
            root = root.right;
        }else{
            successor = root;
            root = root.left;
        }
    }