Check Subtree

T1 and T2 are two very large binary trees, with T1 much bigger than T2. Create an algorithm to determine if T2 is a subtree of T1.

Solution

A deterministic way to represent a binary tree as a single object is with a pre-order traversal. To understand why an in-order traversal will not work, consider that two binary search trees constructed in different orders, but with the same elements, will have the same in-order traversals.