Easy to understand JAVA solution


  • 0

    This solution is based on the following 2 scenarios when trying to find a successor.

    Scenarios 1: "If the right subtree of node p is noneempty, then the successor of p is just the leftmost node in p's right subtree."

    Scenario 2: "If the the right subtree of node p is empty and p has a successor s, then s is the lowest ancestor of p whose left child is also an ancestor of p."

    The above is confusing to me let me explain in my own words. If the node of interest p has a right node its successor is its right nodes min(you are done this is the simple case). Alternatively to find the successor, start at the root node and search down toward the node of interest p saving the successor each time the curr node is larger than p as this is a potential successor.

    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if(root == null || p == null) return null;
        if(p.right != null) return min(p.right);
        TreeNode curr = root, s= null;
        while(curr != null){
            if(curr.val > p.val){
                s= curr;
                curr = curr.left;
            }else curr = curr.right;
        }
        return s;
    }
    private TreeNode min(TreeNode n){
        if(n.left == null)return n;
        return min(n.left);
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.