DSA Factory
Free lessonsTrees · Stage 0 · Nodes and depth · Step 4

Same tree

Walk two trees simultaneously, checking structure and values at every node. About 9 minutes.

Comparing two trees at once

To check that two trees are identical, walk them together in lockstep, like two people following the same directions and comparing what they see at every turn.

At each step you look at one spot in each tree and ask two questions: do both have a node there, and do the nodes hold the same value?

Both empty: both trees ended at the same point: same.
Only one empty: one tree has a node and the other doesn't: different.
p = [1, 2, 3] on the left, q = [1, 2, 3] on the right
123123

Walk both trees in lockstep. Roots: both exist, both hold 1. So far so good.

Move 1 of 4

The recursive step

If neither spot is empty and the two values match, then the trees are identical only if the left subtrees match each other and the right subtrees match each other. Both sides must be the same. A single mismatch anywhere means the answer is no.

Different numbers: in the same position means the trees differ.
Both sides: the left pair and the right pair must both be the same.
In code
if not p and not q:
    return True
if not p or not q:
    return False
if p.val != q.val:
    return False
left = is_same_tree(p.left, q.left)
right = is_same_tree(p.right, q.right)
return left and right
Quick check

If p is null and q is a node with val 1, what does is_same_tree return?

  1. Afalse
  2. Btrue
Show the answer

false. One tree has a node while the other is empty, so their shapes do not match.

Your problem

Same tree

Given the roots of two binary trees p and q, return true if they are structurally identical and have the same node values. Otherwise, return false.

Example
p = [1, 2, 3], q = [1, 2, 3] → true

0 ≤ number of nodes ≤ 10,000 · -1,000,000 ≤ node.val ≤ 1,000,000

Solve it in your browserPython, C++, Java or JavaScript. Hints if you get stuck. No sign-up needed.
Start coding