Solving Subtree of Another Tree in Python: Step-by-Step Guide

Introduction to the Subtree of Another Tree Problem

The "Subtree of Another Tree" problem is a classic algorithmic challenge frequently encountered in coding interviews and competitive programming. Given two binary trees — a root tree and a subRoot tree — the task is to determine whether subRoot is a subtree of root. A subtree is defined as a node in the original tree along with all of its descendants, meaning the structure and values must match exactly.

This problem tests your understanding of tree traversal, recursion, and string matching techniques. In this tutorial, we'll explore multiple approaches to solve it, analyze their time complexities, and discuss best practices for writing clean, efficient Python code.

Why This Problem Matters

Understanding how to solve the subtree problem builds foundational knowledge that applies to many real-world scenarios:

Version control systems: Detecting whether a directory structure exists as a subset within another repository.
DOM manipulation: Checking if a particular HTML fragment exists within a larger document tree.
Compiler design: Pattern matching within abstract syntax trees during optimization passes.
Bioinformatics: Comparing phylogenetic trees to find common evolutionary substructures.

From an interview perspective, this problem elegantly combines two fundamental skills: tree traversal and subtree comparison. Mastering it demonstrates your ability to decompose complex problems into smaller, manageable recursive subproblems.

Defining the Tree Node Structure

Before diving into solutions, let's establish the binary tree node structure we'll use throughout this tutorial. In Python, we typically represent tree nodes using a simple class:

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

Each node stores a value and references to its left and right children. With this structure in place, we can construct trees for testing our solutions.

Approach 1: Recursive Depth-First Search

The most intuitive approach uses recursion. For every node in the root tree, we check whether the subtree starting at that node is identical to subRoot. This breaks down into two subproblems: traversing the main tree and comparing two trees for equality.

Implementing the Tree Comparison Helper

First, we need a helper function that determines whether two trees are identical. Two trees are identical if they have the same structure and corresponding nodes have the same values:

def is_same_tree(s, t):
    # Both nodes are None - trees match
    if not s and not t:
        return True
    # One node is None, the other isn't - mismatch
    if not s or not t:
        return False
    # Values must match, and both subtrees must match
    return (s.val == t.val and
            is_same_tree(s.left, t.left) and
            is_same_tree(s.right, t.right))

This helper follows a straightforward recursive pattern. The base cases handle when both nodes are None (a match) or when only one is None (a mismatch). Otherwise, we compare values and recursively check both children.

Implementing the Main Subtree Check

With the helper in place, the main function traverses every node in the root tree and uses the helper to test for a match:

def is_subtree(root, subRoot):
    # An empty subtree is always a subtree
    if not subRoot:
        return True
    # Non-empty subtree cannot exist in empty tree
    if not root:
        return False
    # Check if trees match at current node
    if is_same_tree(root, subRoot):
        return True
    # Otherwise, recursively check left and right subtrees
    return is_subtree(root.left, subRoot) or is_subtree(root.right, subRoot)

The logic here is elegant. We first handle edge cases where either tree is empty. Then, at each node, we check if a match exists. If not, we recursively search the left and right children. The or operator short-circuits, so we stop as soon as we find a match.

Complete Working Example

Let's put everything together with a complete, testable example:

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


def is_same_tree(s, t):
    if not s and not t:
        return True
    if not s or not t:
        return False
    return (s.val == t.val and
            is_same_tree(s.left, t.left) and
            is_same_tree(s.right, t.right))


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


# Build the main tree:
#       3
#      / \
#     4   5
#    / \
#   1   2
root = TreeNode(3)
root.left = TreeNode(4)
root.right = TreeNode(5)
root.left.left = TreeNode(1)
root.left.right = TreeNode(2)

# Build the subtree:
#     4
#    / \
#   1   2
subRoot = TreeNode(4)
subRoot.left = TreeNode(1)
subRoot.right = TreeNode(2)

print(is_subtree(root, subRoot))  # Output: True

Complexity Analysis

Let m be the number of nodes in the root tree and n be the number of nodes in the subRoot tree. The time complexity is O(m * n) in the worst case because, for each of the m nodes, we may need to compare up to n nodes. The space complexity is O(max(m, n)) due to the recursion stack depth, which corresponds to the height of the trees.

Approach 2: Serialization and String Matching

An alternative approach leverages string serialization. If we serialize both trees into strings, the problem reduces to checking whether the subRoot's serialized string is a substring of the root's serialized string. This approach can be more efficient in practice due to optimized string search algorithms.

Serializing Trees with Delimiters

The key insight is to use a pre-order traversal with special delimiter characters to mark null nodes. Without delimiters, trees with different structures could produce identical strings. Here's the implementation:

def serialize(node):
    if not node:
        return "#"
    # Use a delimiter to separate values and mark structure
    return "," + str(node.val) + serialize(node.left) + serialize(node.right)


def is_subtree_serialized(root, subRoot):
    root_str = serialize(root)
    sub_str = serialize(subRoot)
    return sub_str in root_str

The leading comma before each value is crucial. It prevents false positives where one value is a prefix of another. For example, without delimiters, a node with value 12 could falsely match part of a node with value 1 followed by a node with value 2.

Complete Serialized Example

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


def serialize(node):
    if not node:
        return "#"
    return "," + str(node.val) + serialize(node.left) + serialize(node.right)


def is_subtree_serialized(root, subRoot):
    root_str = serialize(root)
    sub_str = serialize(subRoot)
    return sub_str in root_str


# Main tree:
#       3
#      / \
#     4   5
#    / \
#   1   2
root = TreeNode(3)
root.left = TreeNode(4)
root.right = TreeNode(5)
root.left.left = TreeNode(1)
root.left.right = TreeNode(2)

subRoot = TreeNode(4)
subRoot.left = TreeNode(1)
subRoot.right = TreeNode(2)

print(is_subtree_serialized(root, subRoot))  # Output: True

# Test with a non-matching subtree
fakeSub = TreeNode(4)
fakeSub.left = TreeNode(1)
fakeSub.right = TreeNode(3)
print(is_subtree_serialized(root, fakeSub))  # Output: False

Complexity of the Serialization Approach

Serialization takes O(m) and O(n) time respectively, producing strings of similar length. Python's in operator uses an efficient substring search algorithm, typically running in O(m + n) time on average, though worst-case can be O(m * n) depending on the implementation. The space complexity is O(m + n) for storing the serialized strings.

Approach 3: Using Merkle Hashing

For large trees where performance is critical, we can use a Merkle-like hashing approach. We compute a hash for each subtree based on its structure and values. If the hash of any subtree in the root matches the hash of subRoot, we have a candidate match that we can verify.

import hashlib


def compute_hash(node):
    if not node:
        return "#"
    left_hash = compute_hash(node.left)
    right_hash = compute_hash(node.right)
    # Combine value and children hashes
    combined = str(node.val) + left_hash + right_hash
    return hashlib.sha256(combined.encode()).hexdigest()[:10]


def is_subtree_hashed(root, subRoot):
    target_hash = compute_hash(subRoot)

    def check(node):
        if not node:
            return False
        if compute_hash(node) == target_hash:
            return True
        return check(node.left) or check(node.right)

    return check(root)

This approach shines when you need to perform multiple subtree queries against the same root tree, as you can precompute all hashes once and reuse them. However, for a single query, the overhead of hashing may not provide significant benefits over the simpler recursive approach.

Best Practices and Common Pitfalls

Handle Edge Cases Explicitly

Always consider edge cases before writing your main logic. Common edge cases include:

An empty subRoot — this is technically a subtree of any tree, so return True.
An empty root with a non-empty subRoot — return False.
Both trees empty — return True.
Single-node trees where values match or differ.

Avoid Premature Optimization

The recursive DFS approach is clear, correct, and sufficient for most interview scenarios. Don't jump to serialization or hashing unless you have evidence that the basic approach won't meet performance requirements. Premature optimization adds complexity and potential bugs.

Use Meaningful Variable Names

While s and t are common in textbook implementations, using descriptive names like tree1 and tree2, or root and candidate, improves readability significantly in production code.

Test with Diverse Tree Shapes

Don't just test with balanced trees. Include tests with skewed trees (essentially linked lists), trees with duplicate values, and cases where the subtree appears at various depths. Here's a testing template:

def test_is_subtree():
    # Test 1: Basic match
    root = TreeNode(3, TreeNode(4, TreeNode(1), TreeNode(2)), TreeNode(5))
    sub = TreeNode(4, TreeNode(1), TreeNode(2))
    assert is_subtree(root, sub) == True

    # Test 2: No match
    sub2 = TreeNode(4, TreeNode(1), TreeNode(3))
    assert is_subtree(root, sub2) == False

    # Test 3: Empty subtree
    assert is_subtree(root, None) == True

    # Test 4: Empty root, non-empty subtree
    assert is_subtree(None, sub) == False

    # Test 5: Single node match
    root5 = TreeNode(1)
    sub5 = TreeNode(1)
    assert is_subtree(root5, sub5) == True

    # Test 6: Subtree at leaf level
    root6 = TreeNode(1, TreeNode(2, TreeNode(3)), None)
    sub6 = TreeNode(3)
    assert is_subtree(root6, sub6) == True

    print("All tests passed!")


test_is_subtree()

Consider Iterative Solutions for Deep Trees

Python's default recursion limit is around 1000. For very deep trees, a recursive solution may hit this limit and raise a RecursionError. In such cases, convert your recursive approach to an iterative one using an explicit stack:

def is_subtree_iterative(root, subRoot):
    if not subRoot:
        return True
    if not root:
        return False

    stack = [root]
    while stack:
        node = stack.pop()
        if is_same_tree(node, subRoot):
            return True
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return False

This iterative traversal avoids deep recursion while still using the recursive is_same_tree helper, which is typically safe since the comparison depth is bounded by the subtree size.

Choosing the Right Approach

Each approach has its ideal use case:

Recursive DFS: Best for interviews and most practical scenarios. Easy to explain, implement, and debug.
Serialization: Best when you need to compare trees across different systems or store tree representations for later comparison.
Merkle hashing: Best for repeated subtree queries on the same large tree, such as in version control or synchronization systems.

For most developers, the recursive DFS approach provides the best balance of clarity, correctness, and performance. It directly expresses the problem's recursive nature and handles all edge cases naturally.

Conclusion

Solving the "Subtree of Another Tree" problem in Python reinforces essential tree manipulation skills that transfer to countless other algorithms. The recursive DFS approach offers an elegant, readable solution by decomposing the problem into tree traversal and tree comparison subproblems. For specialized needs like repeated queries or cross-system comparisons, serialization and hashing provide valuable alternatives. By understanding all three approaches and their trade-offs, you'll be well-equipped to tackle this problem in interviews and apply the underlying patterns to broader tree-based challenges in your development work. Remember to always handle edge cases explicitly, test with diverse tree shapes, and choose the simplest approach that meets your performance requirements.