Concise Java O(n) runtime O(1) space with detailed explanation


  • 0
    S

    Using Queue

    If the problem's requirements don't specifically prohibit the usage of extra space, and you can think of a trivial solution using extra space, it's always best not to overcomplicate the solution until you know that optimizations are required.

    With that being said, an extremely trivial solution would be to run through the in-order traversal and save the values in a queue as you traverse through them. The successor will be the element that follows the p node in the queue.

    class Solution {
        public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
            LinkedList<TreeNode> q = new LinkedList<>();
            inorderTraverse(root, q);
            
            while (!q.isEmpty())
                if (q.poll() == p && !q.isEmpty()) 
                    return q.poll();
            
            return null;
        }
        
        private void inorderTraverse(TreeNode node, LinkedList<TreeNode> q) {
            if (node == null) return;
            inorderTraverse(node.left, q);
            q.add(node);
            inorderTraverse(node.right, q);
        }
    }
    

    Runtime is O(n) and space is O(n). But as promised, we can do better!

    Constant Space Solution:

    By examining the rules of in-order traversal, we can establish the following rules about the successor of any given element in the tree:

    • If the current node has a right child, the successor will always be the leftmost child of the current element's right child (or the right element if no left child exists).
    • If the element has no right child, the successor will be the first parent whose left child contains the current element.

    These rules may be hard to follow, so it helps re-reading them and visualizing a few examples:

    0_1520693296942_Screen Shot 2018-03-10 at 9.47.55 AM.png

    The values will be traversed in the following order: 4 2 5 1 3

    Following the first rule for any node that contains a right child:

    • 2's right child's left most child is 5
    • 1's right child's left most child is 3

    Following the second rule:

    • 4 has no right child, so must find the first parent who contains our path on the left side, so in this example, the value 4 is on the left side of 2, so we know 2 is the successor.
    • 5's has no right child, and it's the first parent containing our path on the left is 1 (since 1 contains our value on the right, we keep going until we find a parent containing us on the left).
    • We know 3 is the last element because there is no parent that contains our path on the left (i.e., every chain of parents for the value of 3 contains it's children on the right).

    At last, we have:

    class Solution {
        public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
            if (root == null || p == null) return null;
            if (p.right != null) return findLeftMost(p.right);
            
            TreeNode parent = findParent(root, p), child = p;
            
            while (parent != null && parent.right == child) {
                child = parent;
                parent = findParent(root, parent);
            }
            
            return parent != null && parent.left == child ? parent : null;
        }
        
        private TreeNode findParent(TreeNode node, TreeNode child) {
            if (node == null || child == null) return null;
            if (node.left == child || node.right == child) return node;
            TreeNode left = findParent(node.left, child);
            return left == null ? findParent(node.right, child) : left;
        }
        
        private TreeNode findLeftMost(TreeNode node) {
            return node.left == null ? node : findLeftMost(node.left);
        }
    }
    

    The worst case runtime for this algorithm is O(n^2), if we were given a tree containing only right children (because each parent lookup is O(n) and we would have to do that for each element). Average runtime is O(n) and no extra space is required (outside the stack, which can easily be replaced with a for loop).


Log in to reply
 

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