Same Tree
FreeTreesEasy27 of 75
The problem
Determine whether two binary trees have identical structure and matching values at every corresponding node.
Example
Two roots with value 3 differ if only one has a left child.
Need a hint?
Null positions are part of the structure.
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
If both nodes are null, they match. If exactly one is null or their values differ, they do not. Otherwise require both pairs of left children and both pairs of right children to match recursively.
Complexity
O(min(n, m)) time for nonempty inputs and O(min(h1, h2)) stack space.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.