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 Sam K., 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

More Trees practice problems

See all Trees problems →