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

Problem

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

Solution

Method 1 - Brute force
Traverse T1. If the current node is equal to the root node of T2, traverse both of the trees (T2 and the current subtree of T1) at the same time. Compare the current node. If they are always equal, T2 is a subtree of T1.

Method 2 - Pre-process the tree and store it in cache

I suggest an algorithm, that uses preprocessing:
1) Pre-process the T1 tree, keeping the list of all possible subtree roots (the cache list will have a millions of entries);
2) Sort the cached list of roots by the descending order of data, kept in root. You may choose more elegant sorting function, for example, parse a character tree into string.
3) Use binary search to locate the necessary sub-tree. You may quickly reject subtrees, with the number of nodes, not equal to the T2 number of nodes (or with the different depth).
Note that steps 1) and 2) must be done only once, then you can test many sub-tree candidates, using the same preprocessed result.