-1
$\begingroup$

I have written this solution for finding the Lowest Common Ancestor in a Binary Tree. Now I wanted to find the time complexity of this problem by solving via recurrence relation. Can someone suggest if the approach is correct:

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));
 }}

The recurrence for isChild() is: T(n) = T(n/2) + T(n/2) +1

But I cannot write the recurrence for lowestCommonAncestor(). Can someone please help?

$\endgroup$
  • 1
    $\begingroup$ Hello,I think that coding is off-topic here $\endgroup$ – 3SAT Feb 2 '16 at 20:53
  • 2
    $\begingroup$ Please get rid of the source code and replace it with ideas, pseudo code and arguments of correctness. See here and here for related meta discussions. $\endgroup$ – Raphael Feb 2 '16 at 20:55
  • 2
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – Raphael Feb 2 '16 at 20:55
  • 1
    $\begingroup$ Or are you really asking how to analyse your solution w.r.t. running time cost? $\endgroup$ – Raphael Feb 2 '16 at 20:55
3
$\begingroup$

To analyze the performance of this algorithm. We see what your code does.

You start with the root node. You ask if p is the child a your left subtree, and then you asked if q is the child of your left subtree. You stored them as a variable.

And then in your next 2 if statements, you make 4 more similar checks.

For each is in subtree query, it is obvious that your worst case performance is the size of the subtree.

Suppose the two nodes are not in the tree, then you will always go right. That seems to be a worst case in your algorithm.

So in the worst case, you have a right going chain, and too bad both input never exists in your tree, you will end up spending n^2 time and finally return null.

As a side point, you could do much better in terms of time complexity. Here is an example I done.

http://andrew-algorithm.blogspot.com/2015/07/leetcode-oj-lowest-common-ancestor-of_12.html

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.