Explanation of Java solutions sub-optimal to optimal


  • 0
    L

    I guess the first instinct to solve this problem comes from the most naive way: write the inorder traversal into array and then read the next value from the array. The slightly better version is to read the next value while doing an inorder traversal as below:

    private void helper(TreeNode root, TreeNode p) {
            if(root==null || p==null) {
                return;
            }
            
            helper(root.left,p);
            if(prev!=null && p.val == prev.val) {
                cur = root;
                prev = null;
                return;
            }
            prev = root;
            helper(root.right,p);
        }
    

    The time complexity for the above is O(n) and the space complexity is O(logn). The solution above is clearly not the best solution since it doesn't use the BST property. Can we do better ? Yes, we should do it in O(logn) but there are certain cases that we need to think about in the Inorder traversal.

    case 1: If the key node is the leaf node on the left side, the next node will be its immediate parent.
    case 2: if the key node is the leaf node on the right side, the next node will be one of its parents (including root)
    case 3: Mostly the next node is the leftmost child of the right node of the key node.

    The above could be clarified by drawing some pictures. So essentially, what we need to do is :

    a. Start from the root.
    b. Whenever you find a node that is bigger than the key node, overwrite the successor in a way that you are picking the min of all succcessors.
    c. When a node is lesser than or equal to the key node, go on the right side.

    Here is the iterative version:

    public TreeNode inorderSuccessor_it(TreeNode root, TreeNode p) {
            if(p==null || root==null) {
                return null;
            }
            
            TreeNode suc = null;
            TreeNode temp = root;
            while(temp!=null) {
                if(temp.val>p.val) {
                    suc = temp;
                    temp = temp.left;
                }
                else {
                    temp = temp.right;
                }
            }
            return suc;
        }
    

    Recursive version:

    private TreeNode suc = null;
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        recurse(root,p);
        return suc;
    }
    
    private void recurse(TreeNode root, TreeNode p) {
         if(p==null || root==null) {
            return ;
        }
        if(root.val > p.val) {
            suc = root;
            recurse(root.left,p);
        }
        else {
            recurse(root.right,p);
        }
    }

Log in to reply
 

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