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.

StackExchange Code Review Q#6774, answer score: 6