Skip to main content

572. Subtree of Another Tree

easy

Given two binary trees, return true if one tree contains a subtree that's structurally identical to the other — a classic 'recursion of recursion' question where same-tree check is the helper.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values as subRoot, and false otherwise. A subtree of a binary tree is a tree that consists of a node in the tree and all of this node's descendants.

Constraints

  • The number of nodes in the root tree is in the range [1, 2000].
  • The number of nodes in the subRoot tree is in the range [1, 1000].
  • -10^4 <= root.val, subRoot.val <= 10^4

Examples

Example 1

Input
root = [3,4,5,1,2], subRoot = [4,1,2]
Output
true

Example 2

Input
root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output
false

Example 3

Input
root = [1,1], subRoot = [1]
Output
true

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Write a helper sameTree(a, b) that returns true when two trees match structurally and value-wise.

Hint 2

At every node of root, check whether sameTree(node, subRoot) holds — if not, recurse into left and right.

Hint 3

Watch the base cases: null vs non-null returns false; both null returns true.

Solution approach

Reveal approach

Two recursions. First, sameTree(a, b): if both null return true; if exactly one is null return false; if values differ return false; otherwise recurse on left and right children. Second, the outer walk: if root is null return false; if sameTree(root, subRoot) return true; otherwise return isSubtree(root.left, subRoot) OR isSubtree(root.right, subRoot). Time O(m*n) worst case where m and n are node counts. Space O(h) for the recursion stack. A hash-based serialization approach can hit O(m+n) but the recursive solution is what interviewers expect.

Complexity

Time
O(m*n)
Space
O(h)

Related patterns

  • dfs
  • recursion

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Apple

Practice these live with InterviewChamp.AI

Drill Subtree of Another Tree and Trees problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →