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.
This problem can be solved by the following the steps.
- check first node if T1 and T2 if the two data are identical
- if above condition is true, check the left node and right node as well recursively.
- if above condition is false, start from left node or right node of T1.