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 of subRoot and false otherwise.\n\nA 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.

Approach

Traverse the main tree and, at each node, check whether the subtree rooted there matches subRoot. Use a helper to compare two trees for structural and value equality. If any node matches, return true; otherwise continue searching.

Why It Works

If subRoot appears as a subtree of root, then there exists a node in root whose entire subtree is identical to subRoot. The DFS visits every node and the equality check verifies that exact condition, so the algorithm returns true iff such a node exists.

Complexity

• Time: O(n * m) in the worst case
• Space: O(h) for recursion stack

Reference Implementation (Python)

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        def same(a: Optional[TreeNode], b: Optional[TreeNode]) -> bool:
            if not a and not b:
                return True
            if not a or not b or a.val != b.val:
                return False
            return same(a.left, b.left) and same(a.right, b.right)

        if not root:
            return False
        if same(root, subRoot):
            return True
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)