Subtree of Another Tree

Intuition

A subtree match must start at some node of root, so we simply try every node as a potential anchor. At each anchor we run a helper sameTree that checks whether the two trees are structurally identical with equal values, walking both in lockstep. If any anchor produces a full match we are done; otherwise we recurse into the children of root and keep looking. This costs O(n * m) in the worst case because each of the n root nodes may trigger an O(m) comparison. A faster alternative serializes both trees into strings with explicit null markers and runs a substring search (for example KMP), giving O(n + m); the serialization must use delimiters so that values like 12 and 2 do not accidentally match.

Algorithm walkthrough

1. 1If subRoot is null, treat it as a match and return true.
2. 2If root is null while subRoot is not, return false.
3. 3Run sameTree(root, subRoot): both null is a match, one null or unequal values is a mismatch.
4. 4sameTree recurses on left-with-left and right-with-right children.
5. 5If the current node matches, return true immediately.
6. 6Otherwise recurse: return isSubtree(root.left, subRoot) OR isSubtree(root.right, subRoot).

Implementation

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

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