Data Structure - Whether a Small tree is a Sub-tree of a Large Tree?

In this post, I note the approach and my thought process about determining whether a given smaller tree (t2) is a sub-tree of another larger tree (t1).

First, the approach: Since I know t2 is smaller and it is to be matched/found in a larger tree t1, I'll take the approach of scanning through the larger tree t1, and t1's children, by trying to find a match of t2 in t1's left child tree and find a match of t2 in t1's right child tree, recursively.

---

Thought Process

1. Define the contract of the function for finding sub-tree

boolean subTree(TreeNode t1, TreeNode t2)

2. Consider boundary conditions for finding sub-tree

Consider what if the small tree t2 is null, and what if the bigger tree t1 is null.

3. Put in core logic as mentioned in the above 'approach' section for finding a match so I can say a sub-tree is found.

If t1.data is the same as t2.data, further check if they are the exactly match. However, if t1.data is not the same as t2.data, check if t2 is a sub-tree of t1.left or a sub-tree of t2.left.

4. Implement the logic for checking if 2 trees are exactly the same.

Code Sample

boolean subTree(TreeNode t1, TreeNode t2) {
  if (t2 == null)
    return true;  // boundary condition: the empty tree is always a subtree
  if (t1 == null)
    return false; // boundary condition: big tree empty & subtree still not found.

  if (t1.data == t2.data) {
    if (matchTree(t1,t2))
      return true;
  }
  else{
    return (subTree(t1.left, t2) || subTree(t1.right, t2));
  }
}

// An auxiliary function to determine whether 2 trees are exact match
boolean matchTree(TreeNode t1, TreeNode t2) {
  if (t2 == null && t1 == null)
    return true;  // boundary condition
  if (t1 == null || t2 == null)
    return false; // boundary condition

  if (t1.data != t2.data){
    return false; // data doesn’t match
  }
  else{
    return (matchTree(t1.left, t2.left) && matchTree(t1.right, t2.right));
  }
}