Subtree of Another Tree

Problem

https://leetcode.com/problems/subtree-of-another-tree/

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 ofsubRoot and false otherwise.

A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node’s descendants. The tree tree could also be considered as 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:sup:`4`<= root.val <= 10:sup:`4`

• -10:sup:`4`<= subRoot.val <= 10:sup:`4`

Pattern

Tree, Depth-First Search, String Matching, Binary Tree, Hash Function

Approaches

DFS

Explanation

We can use depth-first search to traverse the tree and check if any of the subtrees are equal to subRoot. If the current node is not equal to subRoot, we try again with the left and right children of the current node until we reach a leaf node.

To check if two trees are equal, we also use depth-first search. Two trees are equal if and only if their roots are equal and their left and right subtrees are equal.

Code

from __future__ import annotations

from collections import deque


class TreeNode:
    """Node in a binary tree."""

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

    @classmethod
    def from_list(cls, vals: list[int | None]) -> TreeNode | None:
        if not vals:
            return None

        root = cls(vals[0])
        queue = deque([root])
        children = iter(vals[1:])

        while queue:
            node = queue.popleft()
            for side in ("left", "right"):
                val = next(children, None)
                if val is not None:
                    child = cls(val)
                    setattr(node, side, child)
                    queue.append(child)

        return root


def isSubtree(root: TreeNode | None, subRoot: TreeNode | None) -> bool:
    """Return whether ``subRoot`` is a subtree of ``root``."""
    if subRoot is None:
        return True

    if root is None:
        return False

    if _same_tree(root, subRoot):
        return True

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


def _same_tree(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

    return (
        p.val == q.val
        and _same_tree(p.left, q.left)
        and _same_tree(p.right, q.right)
    )

Test

>>> from subtree_of_another_tree__dfs import TreeNode, isSubtree
>>> isSubtree(TreeNode.from_list([3, 4, 5, 1, 2]), TreeNode.from_list([4, 1, 2]))
True
>>> root = TreeNode.from_list([3, 4, 5, 1, 2, None, None, None, None, 0])
>>> isSubtree(root, TreeNode.from_list([4, 1, 2]))
False

Complexity

\(m\) is the number of nodes in root, \(n\) is the number of nodes in subRoot, and \(d\) is the maximum depth of root

Measure	Complexity	Notes
Time	\(O(mn)\)	equality check takes \(O(n)\) and we do it for each node in the tree
Auxiliary Space	\(O(d)\)	recursive call stack

class subtree_of_another_tree__dfs.TreeNode(val=0, left=None, right=None)

Bases: object

Node in a binary tree.

classmethod from_list(vals: list[int | None]) → TreeNode | None

subtree_of_another_tree__dfs.isSubtree(root: TreeNode | None, subRoot: TreeNode | None) → bool

Return whether subRoot is a subtree of root.