Subtree of Another Tree

Difficulty: Easy Source: NeetCode

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 of 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. The tree itself is a subtree of itself.

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 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

Prerequisites

Before attempting this problem, you should be comfortable with:

Same Tree Problem — The core check used at every node
DFS — Traversing every node of the main tree as a candidate root
Tree Serialization — Used in the advanced O(m+n) approach

1. Naive DFS + Same Tree Check

At each node of the main tree, check if the subtree rooted at that node is identical to subRoot. We reuse the is_same_tree function from the Same Tree problem. If it matches anywhere, return true.

Algorithm

If root is null, return false (subRoot can’t match nothing)
If is_same_tree(root, subRoot), return true
Otherwise, check is_subtree(root.left, subRoot) or is_subtree(root.right, subRoot)

Solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def is_same_tree(p, q):
    if not p and not q:
        return True
    if not p or not q:
        return False
    if p.val != q.val:
        return False
    return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)

def is_subtree(root, sub_root):
    if not root:
        return False
    if is_same_tree(root, sub_root):
        return True
    return is_subtree(root.left, sub_root) or is_subtree(root.right, sub_root)

# --- helpers ---
def build_tree(values):
    if not values:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    return root

# --- tests ---
root1 = build_tree([3, 4, 5, 1, 2])
sub1 = build_tree([4, 1, 2])
print(is_subtree(root1, sub1))  # True

root2 = build_tree([3, 4, 5, 1, 2, None, None, None, None, 0])
sub2 = build_tree([4, 1, 2])
print(is_subtree(root2, sub2))  # False

root3 = build_tree([1, 1])
sub3 = build_tree([1])
print(is_subtree(root3, sub3))  # True

Complexity

Time: O(m * n) — for each of m nodes in root, we may call same_tree which takes O(n)
Space: O(h) — recursion depth

2. Serialization Approach (O(m + n))

Intuition

Serialize both trees into strings using a preorder DFS with special null markers. Then check if the serialized subRoot string is a substring of the serialized root string. We use markers like #null and # prefixes to avoid false matches (e.g., value 1 matching part of value 12).

Algorithm

Serialize root and subRoot to strings via preorder DFS
Return serialize(subRoot) in serialize(root)

Solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def is_subtree_fast(root, sub_root):
    def serialize(node):
        if not node:
            return "#null"
        # Prefix each value with '#' to avoid partial-number matches
        return f"#{node.val}{serialize(node.left)}{serialize(node.right)}"

    return serialize(sub_root) in serialize(root)

# --- helpers ---
def build_tree(values):
    if not values:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    return root

# --- tests ---
root1 = build_tree([3, 4, 5, 1, 2])
sub1 = build_tree([4, 1, 2])
print(is_subtree_fast(root1, sub1))  # True

root2 = build_tree([3, 4, 5, 1, 2, None, None, None, None, 0])
sub2 = build_tree([4, 1, 2])
print(is_subtree_fast(root2, sub2))  # False

Complexity

Time: O(m + n) for serialization; substring search adds O(m * n) in worst case with naive search, but can be O(m + n) with KMP
Space: O(m + n) — storing the serialized strings

Common Pitfalls

Missing the # prefix on node values. Without it, a tree with value 12 would falsely match a subtree with value 1 followed by 2. The prefix ensures each value is a distinct token.

Checking null incorrectly. is_subtree(null, non-null-subRoot) should return false. If subRoot is null, some definitions return true (empty tree is a subtree of everything) — check the problem statement carefully.

Keyboard shortcuts

Note Book