Subtree of Another Tree
Understanding the Problem
We have two binary trees. We need to determine whether subRoot appears somewhere inside root as a complete subtree. The word "complete" matters here. It is not enough for subRoot to match a portion of some subtree in root. The matching subtree must include every descendant, all the way down to the leaves.
If root has a node with value 4 whose children are 1 and 2, and subRoot is that same structure (4 with children 1 and 2, both leaves), then we have a match. But if node 2 in root has an extra child that subRoot lacks, it is not a match, because the subtree rooted at 4 in root is no longer identical to subRoot.
This problem splits into two sub-tasks: find nodes in root that could be the starting point of a match, and verify whether the subtree rooted at that node is structurally identical to subRoot.
Key Constraints:
1 <= number of nodes in root <= 2000: The root tree is small, so an O(m * n) brute force fits comfortably within time limits (about 2 million node comparisons in the worst case).1 <= number of nodes in subRoot <= 1000: The subtree to match can be up to half the size of the main tree.-10^4 <= node values <= 10^4: Values can be negative. Serialization approaches have to delimit values so that a negative sign or multi-digit number cannot be misread, and hashing approaches accumulate products that exceed 32-bit range, so the hash must be stored in a 64-bit integer.
Approach 1: DFS with Same Tree Check
Intuition
Visit every node in root, and at each node, check whether the subtree rooted there is identical to subRoot. If any node passes, return true. If the traversal finishes without a match, return false.
Checking whether two trees are identical is a recursive problem on its own. Two trees are the same when their root values match, their left subtrees are the same, and their right subtrees are the same. Two null trees also count as the same.
The solution is two recursive functions layered together: one that traverses root looking for candidate match points, and a helper that verifies a match by comparing two trees node by node.
Algorithm
- If
rootis null, return false (there's no subtree to match against). - Check if the tree rooted at
rootis identical tosubRootusing a helper function. - If it is, return true.
- Otherwise, recursively check whether
subRootis a subtree ofroot.leftorroot.right. - The helper function
isSameTreecompares two trees: if both are null, return true. If one is null or values differ, return false. Otherwise, recursively compare left and right children.
Example Walkthrough
Code
- Time Complexity: O(m * n). For each of the m nodes in root, we potentially compare it against all n nodes in subRoot. In the worst case, we do a full comparison at every node.
- Space Complexity: O(h_root + h_sub), the combined heights of the two trees on the recursion stack during an isSameTree check. This is O(m + n) in the worst case for skewed trees and O(log m + log n) for balanced ones.
This brute force repeats partial comparisons at many nodes. The next approach reframes the problem as substring matching: serialize each tree into a string, then check whether one string contains the other.
Approach 2: Tree Serialization with String Matching
Intuition
Convert both trees into strings, then check whether one string contains the other. If we serialize both trees with preorder traversal, including markers for null nodes, then subRoot is a subtree of root if and only if the serialized subRoot appears as a substring of the serialized root.
The serialization needs care. Concatenating raw values creates ambiguity: a node with value 12 would look the same as a node 1 followed by a node 2, and a node with value 2 could match the tail of value 12. We need a delimiter before each value and an explicit marker for null children, so that the string encodes both the values and the shape of the tree without collisions.
In a preorder traversal, every subtree is serialized as one contiguous block: the node, then its entire left subtree, then its entire right subtree, with nothing from outside the subtree in between. So the serialization of the subtree rooted at node X is a contiguous substring of the full serialization. A substring match therefore corresponds to a real subtree match. The delimiter prevents partial-value collisions, and the null markers prevent two trees with the same values but different shapes from producing the same string.
Algorithm
- Serialize
rootinto a string using preorder traversal. For each node, append a delimiter followed by the node's value. For null nodes, append a delimiter followed by a null marker (e.g.,#). - Serialize
subRootthe same way. - Check if the serialized
subRootis a substring of the serializedroot. - If yes, return true. Otherwise, return false.
Example Walkthrough
Code
- Time Complexity: O(m + n) on average, O(m * n) worst case. Serialization takes O(m) for root and O(n) for subRoot. The substring search is typically O(m + n) on average. Using KMP would guarantee O(m + n).
- Space Complexity: O(m + n). We store the serialized strings for both trees, plus recursion stack during serialization.
The serialization approach builds full strings for both trees and relies on substring search. The next approach avoids the strings entirely: it gives each subtree a hash computed from its structure, so comparing two subtrees becomes a single integer comparison.
Approach 3: Tree Hashing (Merkle Hash)
Intuition
This approach borrows the idea behind Merkle trees, used in Git, blockchains, and file systems. Assign each subtree a hash computed from its structure. A leaf's hash depends on its value. An internal node's hash depends on its value combined with the hashes of its left and right children. Two subtrees with the same structure and values produce the same hash, because the hash is built bottom-up from identical inputs at every level.
We compute the hash for every subtree in root and the hash for subRoot, then check whether subRoot's hash appears at any node in root. Each hash combines a node value with two already-computed child hashes, so it costs O(1) per node and O(m + n) overall.
The complication is hash collisions. Two different trees can produce the same hash. When a hash matches, we run a full isSameTree comparison to confirm the match is real. Because that confirmation only runs on the rare hash matches, it does not change the expected running time.
Algorithm
- Compute the hash of
subRootby recursively hashing its tree structure. - Traverse
rootand compute the hash of every subtree. - At each node in
root, check if the subtree hash matchessubRoot's hash. - If a hash match is found, do a full
isSameTreecheck to rule out hash collisions. - Return true if a confirmed match is found, false otherwise.
Example Walkthrough
Code
- Time Complexity: O(m + n) expected. Computing the hash for subRoot takes O(n). Traversing root and computing hashes takes O(m). The isSameTree confirmation runs only on hash matches, which are rare with a good hash function.
- Space Complexity: O(m + n). The recursion stack for hashing root can go up to O(m) deep for a skewed tree, and hashing subRoot up to O(n).