100. Same Tree — DSA Atlas

100

EasyTrees and Binary Search TreesSimultaneous DFS on two treesParallel structural recursion

Same Tree

Given the roots of two binary trees p and q, return true if they are structurally identical and every corresponding pair of nodes has the same value, and false otherwise.

Open official problem prompt ↗

In plain English

Decide whether two binary trees are exact copies of each other in both shape and node values.

Picture it like this

Like overlaying two transparent sheets each printed with a tree: they are 'the same' only if every branch lines up and every label matches when stacked.

Example

Input: p = [1, 2, 3], q = [1, 2, 3]
Output: true
Why: Both trees have root 1 with left child 2 and right child 3, matching in shape and every value.

Constraints

The number of nodes in each tree is in the range [0, 100]-10^4 <= Node.val <= 10^4

Pattern lesson

See the pattern, then code

Parallel structural recursion

↗

Trees and Binary Search Trees

Hierarchies, subtree aggregation, path properties, or ordered tree queries.. Two trees are the same exactly when their roots match in value and, recursively, their left subtrees match and their right subtrees match — a definition that translates straight into recursion.

New words, made simpleKnow these before the algorithm

Structurally identical: Same arrangement of nodes — every present/absent child matches.
Lockstep traversal: Walking both trees at the same time so you always compare corresponding positions.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Serialize and string-compare

Works but allocates extra strings and is easy to get subtly wrong with delimiters.

Serialize both trees (with null markers) and compare the strings.

Time O(n)Space O(n)

Best choiceParallel recursion

Minimal, direct translation of the definition of equality.

Compare roots, then recurse on left pair and right pair.

Time O(n)Space O(h)

The rule we keep true

Invariant

isSameTree(a, b) returns true exactly when the subtrees rooted at a and b are identical, and it is only called on corresponding positions of the two trees.

Why this is correct

Reasoning

Tree equality is defined recursively: two trees are equal iff their roots are both null, or both non-null with equal values and equal left and right subtrees. The code checks each of those cases directly, so by induction on tree height it returns the correct verdict.

The algorithm in three movesSay these aloud before coding

1If both nodes are null, they match (return true)

compare(1,1): equal, recurse

2If exactly one is null or values differ, they mismatch (return false)

compare(2,2): equal; compare(3,3): equal

3Recurse on left children and right children

all match -> true

4Return true only if both recursive comparisons hold

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readp=1, q=1

2 · Askboth null? values equal?

3 · Update state1 == 1

4 · Resultrecurse children

Key takeaway

Corresponding nodes of p and q are compared in lockstep from the roots down.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-4Both null base case
Two empty subtrees are trivially identical.
2
Lines 5-6Mismatch cases
One null but not the other, or differing values, means not the same.
3
Lines 7Recurse and combine
Both left and right subtrees must also be identical.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Both trees empty -> true
One empty, one non-empty -> false
Same values but different shape (e.g. [1,2] vs [1,null,2]) -> false

Common beginner mistakes

Checking values before handling the null cases, causing an AttributeError on None
Comparing only values and ignoring structure
Using 'or' instead of 'and' when combining the two recursive results

Check your understanding

Why must the check `not p or not q` come before `p.val != q.val`?

Same Tree

Same Tree

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Trees and Binary Search Trees