Check if small binary tree T1 is a suibtree of large binary Tree T2

Problem

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

A tree T2 is a subtree of T1 if there exists a node n in T1 such the the subtree of n is identical to T2. That is, if you cut off the tree at node n, the two trees would be identical.

Solution

This problem can be solved by the following the steps.

1. check first node if T1 and T2 if the two data are identical
2. if above condition is true, check the left node and right node as well recursively.
3. if above condition is false, start from left node or right node of T1.

Source Code