Java solution : O(nlgn)


  • 0
    W

    Following logic is used in the solution:-

    Traverse through every element of the left side of the root.

    If both p and q are found, move left. If none are found, move right. If only one of them is found, root is the answer.

    Assuming that tree is sufficiently balanced, traversing takes n/2 time and we repeat this logn time.

    A good catch is to compare the TreeNode reference and not their values, since multiple nodes can have same value and we may get false positive! Below is the code :-

    public class Solution {
        boolean foundP = false;
        boolean foundQ = false;
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root == p || root == q)
                return root;
            prefix(root.left, p, q);
            if(foundP && foundQ) {
                foundP = foundQ = false;
                return lowestCommonAncestor(root.left, p, q);
            } else if(!foundP && !foundQ)
                return lowestCommonAncestor(root.right, p, q);
            return root;
        }
        
        void prefix(TreeNode root, TreeNode p, TreeNode q) {
            if(root == null)
                return;
            if(root == p)
                foundP = true;
            else if(root == q)
                foundQ = true;
            
            prefix(root.left, p, q);
            prefix(root.right, p , q);
        }
    }

  • 0
    M

    if(root == p || root == q)
    return root;

    This is an important part of your solution that you don't address in your summary. Without it,
    [[p],[1,q]] will not return correctly.


  • 0
    T

    One average you are good, but your worst case is O(n^2): each node has left only and p and q are at the lowest levels. I think it's possible O(n) worst/avg time.


  • 0
    W

    @mike3: You are right. It covers the case where a node can be its own ancestor


  • 0
    W

    @TWiStErRob: I am not very sure regarding the runtime complexity of this problem. But let's see. If we consider the tree to be balanced, we could traverse n/2 nodes in the 1st pass, then n/4, n/8, .., so on. So, summing up, n(1 + 1/2 + 1/4 + ... 1/(2^lgn) ) which is less than 2n (using GP). This gives us O(n).

    However, if the tree is totally unbalanced (one node on each level), we could be looking (n -1) + (n - 2) + ... 1 nodes, which gives us O(n^2)


  • 0
    T

    You actually visit each node only once regardless of input in lowestCommonAncestor recursion, only the prefix method skews your runtime a lot. I suggest you try to work those into a single method and a single left-right recursion. Btw, what's the runtime score (in ms) you were given? link


Log in to reply
 

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