← Back to problems Solve on LeetCode → ◆ Tree Patterns See #100 Same Tree →

Subtree of Another Tree

LeetCode 572 • Easy • Trees

Input: root = [3, 4, 5, 1, 2], subRoot = [4, 1, 2] → Output: True
Given two binary trees, check if subRoot is a subtree of root (identical structure and values).

TimeO(m·n)each root node vs subRoot

SpaceO(m+n)outer + inner queues

Checked: 0/5 Outer Q: 0 Peak Q: 0

Candidate

Comparing

In Queue

Matched

Outer Q

empty

Check

—

Result

pending

Speed:

Ready

Press Play to watch outer BFS traverse the root tree, calling isSameTree at each node to check for a subtree match.

✎ 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.

═══ SUBTREE — ITERATIVE BFS ═══

PATTERN ▸ Outer BFS + isSameTree O(m·n) · O(m+n)

① OUTER SETUP

from collections import deque

queue = deque([root])

② OUTER BFS LOOP

while queue:

node = queue.popleft()

③ CHECK — call isSameTree

if self.isSameTree(node, subRoot):

return True

④ ENQUEUE CHILDREN

if node.left: queue.append(node.left)

if node.right: queue.append(node.right)

⑤ NO MATCH

return False

─── isSameTree helper ───

⑥ INNER QUEUE + NULL CHECKS

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

if not n1 and not n2: continue

if not n1 or not n2: return False

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

⑦ INNER ENQUEUE + RETURN

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

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

return True

Vars: queue, node, sq, 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.

═══ SUBTREE — RECURSIVE DFS ═══

PATTERN ▸ DFS outer + isSameTree O(m·n) · O(h)

① BASE — NULL ROOT

if not root: return False

② CHECK CURRENT NODE

if self.isSameTree(root, subRoot):

return True

③ RECURSE LEFT OR RIGHT

return isSubtree(root.left, subRoot) or

isSubtree(root.right, subRoot)

─── isSameTree helper ───

④ BASE CASES

if not p and not q: return True

if not p or not q: return False

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: