Subtree of Another Tree: Multiple Solutions and Complexity Analysis

Subtree of Another Tree: Multiple Solutions and Complexity Analysis

The "Subtree of Another Tree" problem is a classic algorithmic challenge that frequently appears in coding interviews and competitive programming. Given two binary trees — a root tree and a subRoot tree — the goal is to determine whether subRoot is a subtree of root. A subtree is defined as a node in the original tree and all of its descendants. This means the structure and values of the subtree must exactly match the corresponding portion of the larger tree.

This problem matters because it tests several fundamental skills at once: tree traversal, recursive thinking, structural comparison, and complexity analysis. It also opens the door to more advanced techniques like tree serialization and string-matching algorithms, making it an excellent teaching example.

Problem Statement

Formally, given the roots of two binary trees root and subRoot, return true if there exists a subtree of root with the same structure and node values as subRoot, and false otherwise. A subtree must include all descendants of the matched node — a partial match is not sufficient.

Why It Matters

• Interview relevance: It combines recursion, tree traversal, and edge-case handling in a single problem.
• Real-world applications: Subtree matching appears in DOM manipulation, XML/JSON comparison, compiler AST analysis, and version control diffing.
• Algorithmic depth: It can be solved with naive recursion, serialization, or advanced string-matching algorithms like KMP.

Solution 1: Recursive Depth-First Search

The most intuitive approach is to traverse the larger tree and, at every node, check whether the subtree starting at that node is identical to subRoot. We use a helper function isSameTree to perform the structural and value comparison.

Implementation

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: TreeNode, subRoot: TreeNode) -> bool:
        if not root:
            return False
        if self.isSameTree(root, subRoot):
            return True
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q:
            return True
        if not p or not q:
            return False
        if p.val != q.val:
            return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

How It Works

The outer recursive function isSubtree visits every node in root. At each node, it calls isSameTree to verify whether the subtree rooted at that node matches subRoot exactly. If a match is found, it short-circuits and returns true. Otherwise, it recurses into the left and right children.

Complexity Analysis

Let m be the number of nodes in root and n be the number of nodes in subRoot.

• Time complexity: O(m * n) in the worst case. For each of the m nodes in root, we may compare up to n nodes with subRoot.
• Space complexity: O(max(m, n)) due to the recursion stack depth, which is bounded by the height of the trees.

This solution is simple and works well for small to medium-sized trees, but it can be inefficient when the trees are large and contain many similar values, causing repeated comparisons.

Solution 2: Tree Serialization with String Matching

A more elegant approach converts both trees into string representations using a pre-order traversal, then checks whether the serialized subRoot string is a substring of the serialized root string. To avoid ambiguity, we use special delimiters for null nodes and separators between values.

Implementation

class Solution:
    def isSubtree(self, root: TreeNode, subRoot: TreeNode) -> bool:
        def serialize(node):
            if not node:
                return "#"
            # Use a delimiter to avoid value collisions (e.g., 12 and 1,2)
            return "," + str(node.val) + "," + serialize(node.left) + "," + serialize(node.right)

        root_str = serialize(root)
        sub_str = serialize(subRoot)
        return sub_str in root_str

How It Works

The serialize function performs a pre-order traversal, encoding each node's value with leading and trailing delimiters. Null children are encoded as #. The delimiters prevent false positives — for example, the tree with value 12 would not accidentally match a tree with values 1 and 2. Once both trees are serialized, a simple substring check determines whether subRoot is contained within root.

Complexity Analysis

• Time complexity: O(m + n) for serialization, plus O((m + n) * (m + n)) in the worst case for Python's in operator, which uses a naive substring search. In practice, this is often much faster than the recursive approach.
• Space complexity: O(m + n) to store the serialized strings.

This approach is concise and leverages built-in string operations, making it a favorite in interviews where readability and brevity are valued.

Solution 3: Serialization with KMP Algorithm

To eliminate the worst-case quadratic cost of naive substring matching, we can apply the Knuth-Morris-Pratt (KMP) algorithm to the serialized strings. KMP preprocesses the pattern to avoid redundant comparisons, achieving linear-time substring search.

Implementation

class Solution:
    def isSubtree(self, root: TreeNode, subRoot: TreeNode) -> bool:
        def serialize(node):
            if not node:
                return "#"
            return "," + str(node.val) + "," + serialize(node.left) + "," + serialize(node.right)

        root_str = serialize(root)
        sub_str = serialize(subRoot)
        return self.kmp_search(root_str, sub_str)

    def kmp_search(self, text: str, pattern: str) -> bool:
        if not pattern:
            return True
        lps = self.build_lps(pattern)
        i = j = 0
        while i < len(text):
            if text[i] == pattern[j]:
                i += 1
                j += 1
                if j == len(pattern):
                    return True
            else:
                if j != 0:
                    j = lps[j - 1]
                else:
                    i += 1
        return False

    def build_lps(self, pattern: str):
        lps = [0] * len(pattern)
        length = 0
        i = 1
        while i < len(pattern):
            if pattern[i] == pattern[length]:
                length += 1
                lps[i] = length
                i += 1
            else:
                if length != 0:
                    length = lps[length - 1]
                else:
                    lps[i] = 0
                    i += 1
        return lps

How It Works

The KMP algorithm builds a "longest prefix suffix" (LPS) array for the pattern string. This array tells us how far we can safely skip ahead in the pattern when a mismatch occurs, without re-examining characters in the text. By applying KMP to the serialized tree strings, we achieve guaranteed linear-time matching.

Complexity Analysis

• Time complexity: O(m + n) for serialization and O(m + n) for the KMP search, giving an overall O(m + n).
• Space complexity: O(m + n) for the serialized strings and the LPS array.

This is the most efficient solution in terms of asymptotic time complexity and is ideal for very large trees or performance-critical applications.

Best Practices

• Handle edge cases: Always check for empty trees. If subRoot is null, it is technically a subtree of any tree. If root is null but subRoot is not, the answer is false.
• Use delimiters in serialization: Without delimiters, values like 12 and 1,2 can produce identical serialized strings, leading to false positives.
• Choose the right approach: For small trees or interviews, the recursive DFS solution is clear and easy to explain. For large datasets, prefer the KMP-based serialization approach.
• Test thoroughly: Include test cases with identical trees, single-node trees, trees with duplicate values, and cases where the subtree appears deep within the larger tree.
• Avoid premature optimization: Start with the recursive solution, then optimize only if profiling shows it is necessary.

Example Test Cases

def build_tree(values):
    if not values:
        return None
    nodes = [TreeNode(v) if v is not None else None for v in values]
    for i, node in enumerate(nodes):
        if node:
            left_idx = 2 * i + 1
            right_idx = 2 * i + 2
            if left_idx < len(nodes):
                node.left = nodes[left_idx]
            if right_idx < len(nodes):
                node.right = nodes[right_idx]
    return nodes[0]

# Test case 1: subRoot is a subtree
root = build_tree([3, 4, 5, 1, 2])
subRoot = build_tree([4, 1, 2])
print(Solution().isSubtree(root, subRoot))  # True

# Test case 2: subRoot is not a subtree
root = build_tree([3, 4, 5, 1, 2, None, None, None, None, 0])
subRoot = build_tree([4, 1, 2])
print(Solution().isSubtree(root, subRoot))  # False

# Test case 3: identical trees
root = build_tree([1, 2, 3])
subRoot = build_tree([1, 2, 3])
print(Solution().isSubtree(root, subRoot))  # True

Conclusion

The "Subtree of Another Tree" problem is a rich exercise that bridges fundamental tree traversal with more advanced string-matching techniques. The recursive DFS solution offers clarity and is perfectly adequate for most practical scenarios, while the serialization approaches provide a pathway to linear-time performance through KMP. By understanding all three solutions and their trade-offs, developers gain not only the ability to solve this specific problem efficiently but also transferable skills in recursion, serialization, and algorithmic optimization that apply across a wide range of tree and string problems.