Subtree of Another Tree
The problem
Determine whether a nonempty binary tree subRoot appears as an entire subtree of root, with exactly the same node values and null-child structure.
Example
A tree rooted at 8 with leaf children 3 and 10 contains the single-node subtree 10.
Need a hint?
At each candidate root, use the same-tree comparison.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Traverse root. At each node, test whether its whole subtree equals subRoot using value and structure comparison. Return true on any match. If a candidate fails, continue with its children. An empty root cannot contain a nonempty subRoot.
Complexity
O(nm) worst-case time and O(h1 + h2) stack space for the straightforward recursive method.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.