Check if a binary tree is a subtree of another tree

Question

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

Answer 1

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.

Answer 2

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

Answer 3

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.