How do you solve Subtree of Another Tree?

Use a depth-first search (DFS) to traverse every node in root. At each node, invoke a helper function isSameTree to check if the subtree rooted at that node matches subRoot. The isSameTree function recursively compares nodes for equality in value and structure. If a match is found, return true immediately; otherwise, continue searching the left and right subtrees. This guarantees correctness and runs in O(m*n) time in the worst case.

What pattern does Subtree of Another Tree use?

The Pattern: DFS (Recursive Tree Traversal and Comparison) The Heuristic: When checking if one tree is a subtree of another, recursively traverse the larger tree and at each node perform a recursive equality check; this dual-recursion approach leverages DFS to explore all candidate roots and verify subtree identity efficiently.

Subtree of Another Tree — DFS

Q: What is the time complexity of Subtree of Another Tree?

O(m * n). In the worst case, for each of the m nodes in root, the algorithm calls isSameTree which can take up to O(n) time to compare subtrees of size n, resulting in O(m * n) total time.

Problem

Given two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values as subRoot, otherwise return false.

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⁴ ≤ root.val ≤ 10⁴
−10⁴ ≤ subRoot.val ≤ 10⁴

Example

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

Output: true

The subtree rooted at the node with value 4 in root matches subRoot exactly. The algorithm recursively checks if root and subRoot are identical starting at the root node. It finds they are not, so it recursively checks the left and right subtrees of root. When it reaches the node with value 4, it invokes the isSameTree helper, which confirms the two trees are identical in structure and values, returning true.

Approach

Straightforward Solution

A brute-force approach would check every node in root as a potential subtree root and compare it to subRoot. This involves a recursive traversal of root and, for each node, a recursive comparison with subRoot, resulting in O(m*n) time complexity where m and n are the sizes of root and subRoot respectively.

Core Observation

A subtree match requires two conditions: the subtree rooted at some node in root must be structurally identical to subRoot, and all corresponding node values must be equal. This naturally suggests a recursive tree comparison.

Path to Optimal

Preview

The problem breaks down into two recursive tasks: (1) traverse root to find candidate nodes, and (2) for each candidate, check if the subtree matches subRoot exactly. The helper function isSameTree performs the subtree equality check by recursively comparing nodes…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a depth-first search (DFS) to traverse every node in root. At each node, invoke a helper function isSameTree to check if the subtree rooted at that node matches subRoot…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(m * n)

In the worst case, for each of the m nodes in root, the algorithm calls isSameTree which can take up to O(n) time to compare subtrees of size n, resulting in O(m * n) total time.

Space

O(h)

The auxiliary space is O(h), where h is the height of the root tree, due to the recursion stack during DFS traversal and subtree comparison. This does not include input or output space.

Solution

Python

1class Solution:
  def isSubtree(self, root: TreeNode, subRoot: TreeNode) -> bool:
      if not subRoot:
          return True
      if not root:
          return False
      
      if self.isSameTree(root, subRoot):
          return True
      
      return (self.isSubtree(root.left, subRoot) or
              self.isSubtree(root.right, subRoot))
13
  def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
      if not p and not q:
          return True
      if not p or not q or p.val != q.val:
          return False
      
      return (self.isSameTree(p.left, q.left) and
              self.isSameTree(p.right, q.right))

Step-by-Step Solution

1

Return True Immediately if subRoot is Empty

3if not subRoot:
4    return True

Objective

To handle the edge case where subRoot is None, which by definition is a subtree of any tree.

Key Insight

An empty tree is a subtree of any tree, so the algorithm can immediately return true if subRoot is None. This early return simplifies the recursive logic by handling this trivial case upfront.

Interview Quick-Check

State & Boundaries

Check if subRoot is None before any other logic, as this is a base case that guarantees a positive result.

Common Pitfalls & Bugs

Failing to handle an empty subRoot can lead to incorrect false negatives.

2

Return False if root is Empty but subRoot is Not

To handle the edge case where root is None but subRoot is not, meaning subRoot cannot be a subtree.

3

Check if Current Trees are Identical Using isSameTree

To determine if the subtree rooted at the current node in root matches subRoot exactly.

4

Recursively Search Left and Right Subtrees for Matching Subtree

To continue searching for subRoot in the left and right children of the current root node if the current subtree does not match.

5

Define Helper to Compare Two Trees for Exact Equality

To define a reusable helper that determines whether two trees are structurally identical and equal in node values.

6

Recursively Compare Two Trees for Structural and Value Equality

To verify if two trees are exactly the same by recursively comparing node values and their left and right subtrees.

5 more steps with full analysis available on Pro.

Line Analysis

This solution has 5 Critical lines interviewers watch for.

Line 8 Critical

if self.isSameTree(root, subRoot):

Check if the current root and subRoot trees are identical.

This is the critical check that determines if the subtree rooted at the current node matches subRoot exactly, enabling early termination if true.

Line 9 Critical

return True

Return true if the current trees are identical.

Returning immediately upon finding a match avoids unnecessary further traversal, improving efficiency.

Line 15 Critical

if not p and not q:

Check if both nodes are None, indicating identical empty trees.

This base case confirms that two empty trees are identical, forming the foundation of the recursive equality check.

Full line-by-line criticality + rationale for all 15 lines available on Pro.

Test Your Understanding

Why does the algorithm need to check both the current node and recursively its left and right children when searching for the subtree?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Subtree of Another Tree from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Subtree of Another Tree drill

or drill a free problem

1	`class Solution:`
2	`def isSubtree(self, root: TreeNode, subRoot: TreeNode) -> bool:`
3	`if not subRoot:`
4	`return True`
5	`if not root:`
6	`return False`
7
8	`if self.isSameTree(root, subRoot):`
9	`return True`
10
11	`return (self.isSubtree(root.left, subRoot) or`
12	`self.isSubtree(root.right, subRoot))`
13
14	`def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:`
15	`if not p and not q:`
16	`return True`
17	`if not p or not q or p.val != q.val:`
18	`return False`
19
20	`return (self.isSameTree(p.left, q.left) and`
21	`self.isSameTree(p.right, q.right))`