Module 17 · Binary Trees: Recursive DFS and Structural Contracts

166. Same Tree

Bridge · Download this solution · All solutions and shared helpers

Problem

Return whether two binary trees have the same shape and equal values at corresponding nodes. Two empty trees are equal; an empty and nonempty tree are not. Different object identities may still represent equal trees. Do not mutate either input.

Examples

Example 1

same_tree(build_tree([1,2,3]),build_tree([1,2,3]))
=> True

Different objects represent the same structure and values.

Example 2

same_tree(build_tree([1,2]),build_tree([1,None,2]))
=> False

The child appears on different sides.

Example 3

same_tree(None,None)
=> True

Both subtrees are empty.

Reveal the worked solution and reasoning

Why this mechanism works

Compare the pair of current subtrees, not two independent traversal lists. Missing-node positions matter: equal values in different shapes are not the same tree. Resolve absence first, then compare values, then delegate the matching left pair and matching right pair. Short-circuiting stops as soon as a mismatch is proven.

State and boundaries

same_tree(a,b) decides equality of exactly these two corresponding subtrees.

Protocol

If either node is missing, succeed only if both are missing.
Reject unequal current values.
Recursively compare matching left children.
Recursively compare matching right children.

Visualization

tree A: 1 with left child 2
tree B: 1 with right child 2
same values, different missing-child positions -> False

Python implementation

from structures import build_tree

def same_tree(a, b):
    if a is None or b is None:
        return a is b
    return (a.val == b.val and same_tree(a.left, b.left)
            and same_tree(a.right, b.right))

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

same_tree(build_tree([1,2,3]),build_tree([1,2,3]))

L4 same_tree: if a is None or b is None:
a=N1(val=1,left=N2,right=N3); b=N4(val=1,left=N5,right=N6)

L4 same_tree: if a is None or b is None:
a=N2(val=2,left=None,right=None); b=N5(val=2,left=None,right=None)

L4 same_tree: if a is None or b is None:
a=None; b=None

L4 same_tree: if a is None or b is None:
a=None; b=None

L4 same_tree: if a is None or b is None:
a=N3(val=3,left=None,right=None); b=N6(val=3,left=None,right=None)

L4 same_tree: if a is None or b is None:
a=None; b=None

L4 same_tree: if a is None or b is None:
a=None; b=None

Result: True. Different objects represent the same structure and values.

same_tree(build_tree([1,2]),build_tree([1,None,2]))

L4 same_tree: if a is None or b is None:
a=N1(val=1,left=N2,right=None); b=N3(val=1,left=None,right=N4)

L4 same_tree: if a is None or b is None:
a=N2(val=2,left=None,right=None); b=None

Result: False. The child appears on different sides.

Why the solution is correct

The missing-node test decides the base shapes correctly. Two nonempty trees are equal exactly when their root values and both corresponding child trees are equal. The recursive conjunction implements that definition, proving correctness by structural induction.

Time and space

O(min(n,m)+1) worst-case comparisons before exhaustion or mismatch for trees of n and m nodes; O(min(h1,h2)+1) recursive depth. Equal trees require O(n) work.

Common mistakes

Comparing preorder value lists without missing markers loses shape information. Comparing node identity rejects valid deep copies.

Reasoning card

State: same_tree(a,b) decides equality of exactly these two corresponding subtrees.

Invariant: Each call decides equality of exactly its two subtrees.

Decision to rehearse: Compare current pair, then recurse on matching child pairs.

Finish: Recursively compare matching right children

Transfer exercise

Define mirror equality by comparing opposite child sides, then use it to test tree symmetry.