Sharing my 4ms iterative Java solution


  • 0
    P

    Well known algorithm-

    1. If the target node has a right subtree. Then min value from the right subtree is the answer
    2. Otherwise the first parent for which the target node is part of its left subtree is the answer.

    The need for having parent pointers is eliminated by keeping track of possible successor while searching the target node. Below is the code

    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
            if(root == null || p == null)
                return null;
            
            TreeNode candidate = null, current = root;
            while(current != null && current.val != p.val){
                if(current.val > p.val){
                    candidate = current;
                    current = current.left;
                }else
                    current = current.right;
            }
            //TreeNode p not found
            if(current == null)
                return null;
            //No right subtree
            if(current.right == null)
                return candidate;
            
            return findMin(current.right);
            
        }
        
        private TreeNode findMin(TreeNode node){
            while(node.left != null)
                node = node.left;
            return node;
        }
    

Log in to reply
 

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