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

boolean subTree(TreeNode t1, TreeNode t2)

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));

}

}