#572

Easy

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Subtree of Another Tree

Determine if one binary tree is an exact subtree of another by comparing structure and node values recursively.

tree depth first search string matching binary tree hash function

Problem Statement

Given two binary trees, root and subRoot, determine whether subRoot is exactly a subtree of root. A subtree is defined as any node in root and all of its descendants matching subRoot's structure and node values.

Return true if there exists a node in root where the subtree rooted at that node is identical to subRoot. Otherwise, return false. For example, root = [3,4,5,1,2], subRoot = [4,1,2] should return true, whereas root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2] returns false.

Examples

Example 1

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

Output: true

Example details omitted.

Example 2

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

Output: false

Example details omitted.

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].
-104 <= root.val <= 104
-104 <= subRoot.val <= 104

Solution Approach

Recursive Comparison

Traverse each node in root using depth-first search and check if the subtree matches subRoot exactly by recursively comparing node values and child structure.

Hashing Subtrees for Optimization

Use a hash function to encode each subtree's structure and values, then compare hashes to quickly detect matches and reduce repeated subtree comparisons.

Iterative Traversal Alternative

An iterative approach using a stack or queue can simulate recursive DFS traversal to compare potential matching subtrees, useful if recursion depth might be an issue.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity can reach O(m*n) in the worst case for comparing m nodes in root with n nodes in subRoot, but hashing or pruning identical subtrees can reduce comparisons. Space complexity depends on recursion stack depth or storage for subtree hashes.

What Interviewers Usually Probe

Asks whether recursion or iterative traversal is preferable for subtree comparison.
Checks if null node handling is correctly implemented in the DFS solution.
Mentions optimization using subtree serialization or hashing techniques.

Common Pitfalls or Variants

Common pitfalls

Failing to check both left and right children for exact match leading to false positives.
Confusing a node with identical value as a valid subtree without matching the full structure.
Exceeding recursion limits on deeply nested trees without iterative fallback.

Follow-up variants

Determine if a tree is a mirror subtree of another, requiring reversed child comparisons.
Count the total number of occurrences where subRoot appears as a subtree within root.
Check if subRoot appears as a subtree in a forest of multiple disconnected trees.

FAQ

What is the most efficient way to check if one tree is a subtree of another?

Use recursive DFS traversal and optional subtree hashing to compare structure and node values efficiently.

Can iterative traversal replace recursion for the subtree check?

Yes, iterative DFS or BFS using a stack or queue can replace recursion and prevent stack overflow in deep trees.

Why do some implementations give false positives?

False positives often occur when only node values are compared without checking the full subtree structure.

How does hashing improve subtree comparison?

Hashing encodes subtree structures and values into a single representation, allowing quick equality checks instead of repeated recursive comparison.

Does this problem pattern involve string matching?

Yes, comparing serialized or hashed subtrees is similar to string matching, making pattern detection efficient.

terminal

Solution

Solution 1: DFS

We define a helper function $\textit{same}(p, q)$ to determine whether the tree rooted at $p$ and the tree rooted at $q$ are identical. If the root values of the two trees are equal, and their left and right subtrees are also respectively equal, then the two trees are identical.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        def same(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
            if p is None or q is None:
                return p is q
            return p.val == q.val and same(p.left, q.left) and same(p.right, q.right)

        if root is None:
            return False
        return (
            same(root, subRoot)
            or self.isSubtree(root.left, subRoot)
            or self.isSubtree(root.right, subRoot)
        )

Continue Practicing

#563 binary tree tilt #538 convert bst to greater tree #606 construct string from binary tree