Lowest Common Ancestor in a Binary Tree. Time Limit Exceeded

Question

I have written this solution for finding the LCA of a Binary Tree.It gives time limit exceeded on the bigger inputs. Can someone please point out a problem in this piece of code. This problem is from Leetcode OJ.

public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if(root == null){
        return null;
    }if((p.val == root.val) || (q.val == root.val)){
        return root;
    } 
    if(root.left == null && root.right == null){
        return null;
    }
    boolean leftChildP = isLeftChild(root,p);
    boolean leftChildQ = isLeftChild(root,q);

    if(isRightChild(root,p) && isLeftChild(root,q)){
        return root;
    }if(isRightChild(root,q) && isLeftChild(root,p)){
        return root;
    }
    if(leftChildP && leftChildQ){
            return lowestCommonAncestor(root.left,p,q);
    }
    return lowestCommonAncestor(root.right,p,q);}


private boolean isLeftChild(TreeNode root, TreeNode node){
    return isChild(root.left,node);
}


private boolean isRightChild(TreeNode root, TreeNode node){
     return isChild(root.right,node);   
}


private boolean isChild(TreeNode parent, TreeNode child){
    if(parent == null){
        return false;}
    if(parent.val == child.val){
        return true;
    }return (isChild(parent.left,child) || isChild(parent.right,child));
}}

Answer 1

The code you have written has complexity O(n^2).

You can find LCA in O(n) in two ways

1.) Store root to node path(in an ArrayList or can use hashset) for both the nodes (p and q). Now start comparing nodes in both paths starting from root(the path till the LCA should match for both p and q), so the node just before when the mismatch occurs in the paths will be the LCA. This solution should work in O(n).

2.) Other solution works on an assumption that if only one node out of p and q exits in your tree then your lca function will return that node. Here is the code that you can do

public BinaryTreeNode<Integer> lca(BinaryTreeNode<Integer> root, int data1, int data2){ if(root == null){ return null; } if(root.data == data1 || root.data == data2){ return root; } BinaryTreeNode<Integer> leftAns = lca(root.left, data1 , data2); BinaryTreeNode<Integer> rightAns = lca(root.left, data1 , data2); / // If you are able to find one node in left and the other in right then root is LCA if(leftAns!= null && rightAns != null){ return root; } if(leftAns!=null){ return leftAns; } else{ return rightAns; } }

This also has time complexity O(n)

Answer 2

A recursive lowestCommonAncestor is calling a recursive isChild... Very brief examination suggests it's O(n^2). It will be time consuming...

Try building a hashset of all ancestors of p - this might cost you O(n), but typically O(logn). Then traverse up from q looking for an a common ancestor. Assuming that the lookup in hashset costs O(1), this will cost you again - O(n), but typically O(logn).

You'll end up with typical complexity of O(logn) - which is better...