Check Subtree

Question 8: 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.

One way we can solve this is to search through the larger tree, and see if we find the root node of the smaller tree. If we do find the root node, we can call a method to check whether the subtree of T1 matches T2.

Below is an algorithm that implements the solution:

We’re done!

Similar Questions:

• Random Node

• Paths With Sum

• Unique BSTs