Blind 75 / Trees / Subtree of Another Tree

Subtree of Another Tree

EasyTrees
Asked byAmazonFacebookMicrosoftGoogle

Problem

Given the roots of two binary trees root and subRoot, determine whether subRoot appears as an exact subtree of root — a subtree that matches subRoot's structure and node values exactly, starting from some node in root.

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

Constraints

  • The number of nodes in root is in the range [1, 2000].

Solve it in the editor. Sign in free to run your Python or JavaScript against test cases, get a verdict, and track your attempts.

Solve on FeatCode →

How to approach it: the Trees pattern

A tree is a hierarchical structure where each node has at most a fixed number of children (two, for binary trees). Almost every tree problem reduces to a traversal — decide what order you visit nodes in, and what you do at each one.

Look for this pattern when

  • The problem is naturally recursive: "the answer for this tree depends on the answer for its subtrees."
  • You need level-by-level information (BFS) versus depth-first structural information (DFS).

Read the full Trees guide →

Video walkthroughs

Original problem on LeetCode ↗

More Trees problems

← Same TreeLowest Common Ancestor of a Binary Search Tree →