8
\$\begingroup\$

I am doing a refresher on algorithms.
I tried to solve the problem of determining if you have 2 trees (T1 and T2), one is a subtree of the other.

I came up with the following:

public boolean isSubtree(Node n1, Node n2){

   if(n2 == null) //Empty Subtree is accepted   
      return true;  

   if(n1 == null)  
      return false;  


   //If roots are equal, check subtrees  
   if(n1.data == n2.data){  
       return isSubTree(n1.left, n2.left) && isSubTree(n1.right, n2.right);  
   }
   else{//No match found for this root. Check subtrees
       return isSubTree(n1.left, n2) || isSubTree(n1.right, n2);  
   }

}

I think it is correct.
Just to clarify n1 is the root of the tree and n2 the root of the subtree we search for.
I was wondering if someone could review it please? Besides correctness the following trouble me:

How would I calculate its complexity?
Also by Googling I found code for this which was similar to mine but not exactly the same.
For example the code fragments I found had if(n1 == null) return false; while I also check if the n2 is not null.
Mu rationale is that an empty tree and an empty subtree should return true.
But either my logic is wrong or the code posts I found on the internet usually ignore this case.

Any input is highly appreciated

\$\endgroup\$
5
\$\begingroup\$

The approach is fundamentally flawed. If you're going to do it this way, you need two methods:

public boolean equals(Node n1, Node n2) {
    if (n1 == n2) return true;
    if (n1 == null || n2 == null) return false;
    if (n1.data != n2.data) return false; // Should use .equals if Node.data isn't primitive
    return equals(n1.left, n2.left) && equals(n1.right, n2.right);
}

public boolean isSubtree(Node n1, Node n2) {
    if (n2 == null) return true;
    if (n1 == null) return false;
    return equals(n1, n2) || isSubtree(n1.left, n2) || isSubtree(n1.right, n2);
}

If you're worried about complexity, you might want to consider whether you can flatten your tree into a canonical (wlog) prefix-order string and use an advanced string matching algorithm.

\$\endgroup\$
  • \$\begingroup\$ @ Peter:Thank you for the reply.This seems very similar to my post.So what is the fundamental error in my approach? \$\endgroup\$ – user384706 Dec 14 '11 at 21:08
  • 1
    \$\begingroup\$ @user384706, you're looking for a subtree which is equal to n2 but you're trying to do it without a tree equality test. The results of isSubtree(n1.left, n2.left) and isSubtree(n1.right, n2.right) can never give enough information to determine whether equals(n1, n2). \$\endgroup\$ – Peter Taylor Dec 14 '11 at 22:11
  • \$\begingroup\$ @user384706, Peter is right. Your method of checking whether something is a subtree is just plain wrong. My counter-examples to your algorithm were attempting to bring you to this realization. \$\endgroup\$ – Winston Ewert Dec 15 '11 at 5:22
  • \$\begingroup\$ @ Peter:I think your code is not correct.I mean there is a problem in the equals method.2 trees with same root but different subtrees will be considered as equal in your method I believe \$\endgroup\$ – user384706 Dec 17 '11 at 16:57
  • \$\begingroup\$ @user384706, I don't think so: the equals method just translates the definition of tree equality into code. But if you think there's a bug, try to find a test case which demonstrates it. \$\endgroup\$ – Peter Taylor Dec 17 '11 at 19:28
3
\$\begingroup\$

The variable names n1 and n2 are poor choices. I mean, you even had to clarify what they meant in your questions. How about just picking names which indicate what they are for.

Rather then assigning to result and returning that, just have two return statements.

If you reverse the order of the two tests, you can leave off the n2 != null expression. Because n2 has already been tested, you know its not NULL. I think you'll find this brings your code into line with the other snippets you found.

Additionally, I think your algorithm gets several cases wrong:

    0           0
   / \         / \ 
  1   2       3   2
 / \
3   4

I believe this will be considered a match by your algorithm. However, it is not. (Depending on your definition of subtree)

    0           0
   / \         / \ 
  0   2       3   4
 / \
3   4

I believe this will not be considered a match by your algorithm. It clearly is.

EDIT

I think you are now missing this case:

    0            1
   / \          / 
  1   2        3
 /
3
\$\endgroup\$
  • \$\begingroup\$ @ Winston:+1.Thank you for your answer.I edited the code.I believe now it catches the cases you correctly mention.Is it correct?Also if it is, how would I calculate the running time?It clearly visits each node more than once, but I am not sure how many times each \$\endgroup\$ – user384706 Dec 12 '11 at 21:02
  • 1
    \$\begingroup\$ @user384706, I think that takes care of the second case, but not the first case. \$\endgroup\$ – Winston Ewert Dec 12 '11 at 23:43
  • \$\begingroup\$ @ Winston: I cannot see, that the first case is not caught.It will start comparing 0 then branch left and compare 1 and 3.This returns false and the second part of && is not evaluated.I.e. to branch right.So it will hit the last line and start branching left so compare 1 and 0 which is false and then compare 2 and 0 and again false \$\endgroup\$ – user384706 Dec 13 '11 at 16:30
  • \$\begingroup\$ @user384706, misread your code. I think you've got a different problem now. See Edit. \$\endgroup\$ – Winston Ewert Dec 14 '11 at 0:57
  • \$\begingroup\$ @ Winston:You are right again!I thinked this is correct now (I hope so!).BTW I noticed that after you updated your answer it is not possible to upvote again.I thought I should be able to do it since the answer was edited \$\endgroup\$ – user384706 Dec 14 '11 at 16:40
1
\$\begingroup\$

A quick optimization to would be to check their sizes before you even start comparing nodes' values; If tree A is bigger than tree B, A obvisouly can't be a subtree of B, and in these cases you can return an answer in constant time.

This would off course require that your trees have a field that keeps track of how many nodes you have added to them, which could prove helpful for many other applications as well.

\$\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.