Subtree of Another Tree

Problem

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.

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^4 <= root.val <= 10^4
-10^4 <= subRoot.val <= 10^4

Solution

###Approach: DFS with Tree Comparison

The key insight is to check at each node of the main tree whether the subtree starting there matches the subRoot tree.

Implementation

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

        if not root:
            return False

        # Check if trees match at current root
        if isSameTree(root, subRoot):
            return True

        # Check left and right subtrees
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

Complexity Analysis

Time Complexity: O(m * n), where m is the number of nodes in root and n is the number of nodes in subRoot. In the worst case, we check all m nodes and for each, we compare n nodes.
Space Complexity: O(h), where h is the height of root (recursion stack).

Key Insights

Two-Level Recursion: We traverse the main tree and at each node, we check if it’s the root of a matching subtree.
Reuse isSameTree: We can reuse the logic from the “Same Tree” problem to check if two trees match.
OR Logic: If the current node matches OR if the subtree exists in left OR right child, we return true.
Base Case: If root is None but subRoot exists, there’s no subtree to match.
Subtree vs Subset: A subtree must include all descendants of a node, not just some nodes.