← Back to problems Solve on LeetCode → ◆ Tree Patterns See #104 Max Depth →

Same Tree

LeetCode 100 • Easy • Trees

Input: p = [1, 2, 3, 4, 5], q = [1, 2, 3, 4, 5] → Output: True
Given two binary trees, check if they are structurally identical with the same node values.

TimeO(n)visit each node pair

SpaceO(n)queue of pairs

Matched: 0/5 Queue: 0 Peak Q: 0

Comparing

In Queue

Matched

Link

Queue

empty

Pair

—

Result

pending

Speed:

Ready

Press Play to watch BFS compare two trees pair-by-pair, or Step to advance one operation.
Uses a deque of node pairs comparing corresponding positions in both trees.

✎ Whiteboard

Size:3

⌨ Type It — Iterative BFS

Practice until you don't need to look. The green highlights are the nuances to burn into memory.

═══ SAME TREE — ITERATIVE BFS ═══

PATTERN ▸ BFS with node pairs O(n) · O(n)

① SETUP

from collections import deque

queue = deque([(p, q)])

② BFS LOOP

while queue:

n1, n2 = queue.popleft()

③ BOTH NULL → SKIP

if not n1 and not n2: continue

④ STRUCTURE MISMATCH → FALSE

if not n1 or not n2: return False

⑤ VALUE MISMATCH → FALSE

if n1.val != n2.val: return False

⑥ ENQUEUE CHILDREN

queue.append((n1.left, n2.left))

queue.append((n1.right, n2.right))

⑦ ALL MATCHED

return True

Vars: queue, n1, n2

▼ your implementation ▼

Verify your solution:

⌨ Type It — Recursive DFS

Practice until you don't need to look. The green highlights are the nuances to burn into memory.

═══ SAME TREE — RECURSIVE DFS ═══

PATTERN ▸ Compare nodes pairwise O(n) · O(h)

① BASE — BOTH NULL

if not p and not q: return True

② STRUCTURE CHECK

if not p or not q: return False

③ VALUE CHECK

if p.val != q.val: return False

④ RECURSE BOTH SUBTREES

return isSameTree(p.left, q.left) and

isSameTree(p.right, q.right)

▼ your implementation ▼

Verify your solution: