Subtree of Another Tree

“Is subRoot a subtree of root?” reduces to “does any node in root start an identical tree to subRoot?” — that reuses the exact same-tree check from the Same Tree problem, just run at every candidate node.

Brute Force (same-tree check at every node)

Time O(m * n)Space O(h)

Walk root with DFS. At each node, run a full isSameTree comparison against subRoot. If any node matches, subRoot is a subtree.

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 | None, subRoot: TreeNode | None) -> bool:
        if root is None:
            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 | None, q: TreeNode | None) -> bool:
        if p is None and q is None:
            return True
        if p is None or q is None:
            return False
        if p.val != q.val:
            return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

Tracing root = [3,4,5,1,2], subRoot = [4,1,2] — isSameTree is tried at each node of root until one matches:

1 / 2

seenresultdiscarded

isSameTree(root=3, subRoot=4): values 3 != 4, mismatch. Not a match at this node -- recurse into children instead.

Complexity: in the worst case, isSameTree (O(n), the size of subRoot) is attempted at every one of the m nodes of root → O(m * n) time. Recursion depth is the height of root → O(h) space.

Serialize + Substring Search

OptimalTime O(m + n)Space O(m + n)

Serialize both trees to strings that uniquely encode structure (using explicit null markers and separators so no value can be mistaken for a different shape), then subRoot is a subtree of root exactly when its serialization is a substring of root’s. Python’s in operator uses an efficient substring search under the hood, giving a near-linear check.

class Solution:
    def isSubtree(self, root: TreeNode | None, subRoot: TreeNode | None) -> bool:
        def serialize(node: TreeNode | None) -> str:
            if node is None:
                return ",#"
            return f",{node.val}{serialize(node.left)}{serialize(node.right)}"

        return serialize(subRoot) in serialize(root)

Why prefer this: each tree is serialized once in O(m) / O(n) time, and the substring search is near-linear in practice → O(m + n) time overall versus the brute force’s O(m * n). The , separator and # null-marker prevent false matches like value 12 accidentally matching inside value 312. Space grows to hold both serialized strings → O(m + n).