LeetCode 572: Subtree of Another Tree

Problem Restatement

We are given the roots of two binary trees:

Return True if there is a subtree of root that has exactly the same structure and node values as subRoot.

A subtree means a node and all of its descendants. A tree is also considered a subtree of itself. The official constraints say the number of nodes in root is in the range [1, 2000], the number of nodes in subRoot is in the range [1, 1000], and node values are between -10^4 and 10^4.

Input and Output

Example function shape:

def isSubtree(root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
    ...

Examples

Example 1:

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

The tree rooted at value 4 inside root is:

    4
   / \
  1   2

This is exactly the same as subRoot.

So the answer is:

True

Example 2:

root = [3, 4, 5, 1, 2, None, None, None, None, 0]
subRoot = [4, 1, 2]

There is a node with value 4, but its subtree is:

    4
   / \
  1   2
     /
    0

This is not the same as subRoot, because the node 2 has an extra child.

So the answer is:

False

First Thought: Compare subRoot at Every Node

A subtree of root must start at some node in root.

So a direct approach is:

1. Visit every node in root.
2. At each node, check whether the subtree starting there is identical to subRoot.
3. Return True if any comparison matches.

This naturally gives us two recursive functions:

Key Insight

There are two different questions:

First, are these two trees identical?

Second, does this smaller tree appear anywhere inside the larger tree?

The first question is solved by comparing two trees node by node.

The second question is solved by DFS over root.

At each node of root, we ask the first question.

Identical Tree Check

Two binary trees are identical if all three conditions hold:

1. Their roots are both missing, or both present.
2. Their root values are equal.
3. Their left subtrees and right subtrees are identical.

In code:

sameTree(a.left, b.left)
sameTree(a.right, b.right)

Both recursive checks must be true.

Algorithm

1. Define sameTree(a, b):

   1. If both are None, return True.
   2. If only one is None, return False.
   3. If a.val != b.val, return False.
   4. Return whether the left subtrees match and the right subtrees match.

2. Define isSubtree(root, subRoot):

   1. If root is None, return False.
   2. If sameTree(root, subRoot) is true, return True.
   3. Otherwise, search root.left.
   4. Otherwise, search root.right.

Correctness

The helper sameTree(a, b) returns True exactly when the two trees have the same structure and the same values. It checks the current nodes first, then recursively checks the left and right children. If one side has a node where the other side has no node, it returns False, so structural differences are detected.

The main function visits every possible root node of a subtree inside root. For each visited node, it calls sameTree to check whether the subtree rooted at that node is identical to subRoot.

If the algorithm returns True, then it found a node in root whose full subtree matches subRoot, so subRoot is a subtree.

If the algorithm returns False, then every possible subtree root in root was checked and none matched subRoot. Therefore, subRoot is not a subtree of root.

Complexity

Let:

Here h is the height of the recursion stack. In a skewed tree, this can be O(n + m) during nested recursive calls.

Implementation

from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val: int = 0, left: Optional['TreeNode'] = None, right: Optional['TreeNode'] = None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def isSubtree(
        self,
        root: Optional['TreeNode'],
        subRoot: Optional['TreeNode'],
    ) -> bool:
        def sameTree(
            a: Optional['TreeNode'],
            b: Optional['TreeNode'],
        ) -> bool:
            if a is None and b is None:
                return True

            if a is None or b is None:
                return False

            if a.val != b.val:
                return False

            return sameTree(a.left, b.left) and sameTree(a.right, b.right)

        if root is None:
            return False

        return (
            sameTree(root, subRoot)
            or self.isSubtree(root.left, subRoot)
            or self.isSubtree(root.right, subRoot)
        )

Code Explanation

The helper handles empty trees first:

if a is None and b is None:
    return True

if a is None or b is None:
    return False

Both missing means the structures match at this position. One missing means the structures differ.

Then we compare values:

if a.val != b.val:
    return False

If the current nodes match, both child pairs must also match:

return sameTree(a.left, b.left) and sameTree(a.right, b.right)

The main search stops when the larger tree is exhausted:

if root is None:
    return False

Otherwise, it checks the current node as a possible subtree root, then searches the left and right subtrees.

Serialization Version

Another approach is to serialize both trees with null markers, then check whether the serialized subRoot appears inside the serialized root.

The null markers are important. Without them, different tree shapes can produce ambiguous strings.

class Solution:
    def isSubtree(
        self,
        root: Optional['TreeNode'],
        subRoot: Optional['TreeNode'],
    ) -> bool:
        def serialize(node: Optional['TreeNode']) -> str:
            if node is None:
                return "#"

            return (
                "^"
                + str(node.val)
                + ","
                + serialize(node.left)
                + ","
                + serialize(node.right)
            )

        return serialize(subRoot) in serialize(root)

The recursive comparison version is usually clearer for this problem.

Testing

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

def run_tests():
    s = Solution()

    root = TreeNode(
        3,
        TreeNode(4, TreeNode(1), TreeNode(2)),
        TreeNode(5),
    )
    subRoot = TreeNode(4, TreeNode(1), TreeNode(2))
    assert s.isSubtree(root, subRoot) is True

    root = TreeNode(
        3,
        TreeNode(4, TreeNode(1), TreeNode(2, TreeNode(0))),
        TreeNode(5),
    )
    subRoot = TreeNode(4, TreeNode(1), TreeNode(2))
    assert s.isSubtree(root, subRoot) is False

    root = TreeNode(1)
    subRoot = TreeNode(1)
    assert s.isSubtree(root, subRoot) is True

    root = TreeNode(1, TreeNode(1))
    subRoot = TreeNode(1)
    assert s.isSubtree(root, subRoot) is True

    root = TreeNode(1, None, TreeNode(1))
    subRoot = TreeNode(1, TreeNode(1))
    assert s.isSubtree(root, subRoot) is False

    print("all tests passed")

run_tests()