## Determine if a small tree is the subtree of a huge tree

You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.

My initial thoughts:
Let us denote the huge tree as T1 and the small tree as T2. We iterate through T1 to see if any node matches the root node of T2. If there’s match, we check if the subtree of T1 is identical to T2. If not, we recursively go deeper.

My initial codes:

```	public static boolean isSubtree(BinaryTreeNode<Integer> T1,
BinaryTreeNode<Integer> T2) {
if (T1 == null)
return false;
else if (T1.getValue().equals(T2.getValue()) && isTwoTreeEqual(T1, T2)) {
return true;
} else {
return isSubtree(T1.getLeft(), T2) || isSubtree(T1.getRight(), T2);
}
}

public static boolean isTwoTreeEqual(BinaryTreeNode<Integer> root1,
BinaryTreeNode<Integer> root2) {
if (root1 == null && root2 == null)
return true;
else if (root1.isLeaf() && root2.isLeaf())
return root1.getValue().equals(root2.getValue());
else if (!root1.isLeaf() && !root2.isLeaf()) {
if (!root1.getValue().equals(root2.getValue()))
return false;
return isTwoTreeEqual(root1.getLeft(), root2.getLeft())
&& isTwoTreeEqual(root1.getRight(), root2.getRight());
} else
return false;
}

It works for small trees. When the size goes to 1000, it nearly never finishes. BAD.
Solutions:
public static boolean containsTree(BinaryTreeNode<Integer> t1,
BinaryTreeNode<Integer> t2) {
if (t2 == null)
return true; // The empty tree is always a subtree
else
return subTree(t1, t2);
}

private static boolean subTree(BinaryTreeNode<Integer> r1,
BinaryTreeNode<Integer> r2) {
if (r1 == null)
if (r1.getValue() == r2.getValue()) {
if (matchTree(r1, r2))
return true;
}
return (subTree(r1.getLeft(), r2) || subTree(r1.getRight(), r2));
}

private static boolean matchTree(BinaryTreeNode<Integer> r1,
BinaryTreeNode<Integer> r2) {
if (r2 == null && r1 == null)
return true; // nothing left in the subtree
if (r1 == null || r2 == null)
if (r1.getValue() != r2.getValue())
return false; // data doesn’t match
return (matchTree(r1.getLeft(), r2.getLeft()) && matchTree(
r1.getRight(), r2.getRight()));
}

The solution is very similar to mine except that it handles the case where T2 is null.

__ATA.cmd.push(function() {
__ATA.initVideoSlot('atatags-370373-5b2deb0541b34', {
sectionId: '370373',
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942-5b2deb0541b7b',  {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160-5b2deb0541b7f',  {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});