DSA problem
Subtree of Another Tree
Given the roots of two binary trees root and subRoot, return true if there is any subtree of root that is structurally identical and node-wise equal to subRoot. A subtree of a tree consists of a node and all of that node's descendants — the subtree must match subRoot exactly in shape and values.
This decomposes naturally into two preorder traversals. First, define isSame(a, b) that decides whether two subtrees are identical (the standard Same-Tree recurrence). Then walk root in preorder: at each node, ask "does isSame(node, subRoot) return true?" If so, return true. Otherwise, recurse into the left and right children.
Each call to isSame costs O(s) where s is the size of subRoot. We may invoke it at every one of the n nodes of root, giving a worst-case time of O(n * s). The space is O(h) for the outer recursion plus O(min(h, h_sub)) for the inner check — overall O(h).
An asymptotically faster technique serializes both trees to strings (with explicit null markers and delimiters to avoid ambiguities like "12" matching the start of "123") and then runs KMP substring search, giving O(n + s). For most inputs the simple recursive version is preferred for clarity, and the LeetCode test suite passes comfortably with it.
Examples
root = [3,4,5,1,2], subRoot = [4,1,2]trueroot = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]falseroot = [1,1], subRoot = [1]trueConstraints
- The number of nodes in root is in the range [1, 2000].
- The number of nodes in subRoot is in the range [1, 1000].
- -10^4 <= root.val, subRoot.val <= 10^4
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.