# Check if a binary tree is a subtree of another tree

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

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.

• @ Peter:Thank you for the reply.This seems very similar to my post.So what is the fundamental error in my approach? Dec 14, 2011 at 21:08
• @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). Dec 14, 2011 at 22:11
• @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. Dec 15, 2011 at 5:22
• @ 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 Dec 17, 2011 at 16:57
• @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. Dec 17, 2011 at 19:28

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.

    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

• @ 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 Dec 12, 2011 at 21:02
• @user384706, I think that takes care of the second case, but not the first case. Dec 12, 2011 at 23:43
• @ 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 Dec 13, 2011 at 16:30
• @user384706, misread your code. I think you've got a different problem now. See Edit. Dec 14, 2011 at 0:57
• @ 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 Dec 14, 2011 at 16:40

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.