Subtree of Another Tree: The Serialization Trick

The naive way to check whether one tree hides inside another is to stand at every node of the big tree and run a full "are these identical?" comparison. It works, but it re-walks overlapping regions again and again. There's a slicker reframe: turn each tree into a single string, then ask a question strings are great at answering — is one a substring of the other?

That one move collapses a tree problem into a text problem. It's the same instinct behind Merkle trees and content-addressed storage: if you can serialize a structure into a canonical fingerprint, structural questions become string questions.

The problem#

Given the roots of two binary trees, root and subRoot, return true if there is a subtree of root that is structurally identical and equal in values to subRoot. A subtree means a node in root plus all of its descendants — you can't match a partial fragment.

The 4-1-2 shape rooted at root's left child matches subRoot exactly, so the answer is true. Two traps live in the definition: the match must go all the way down (leaves included), and node values matter, not just shape.

The brute force baseline#

The direct approach: for every node in root, test whether the subtree anchored there equals subRoot with a node-by-node isSameTree check.

This is correct, but expensive. If root has n nodes and subRoot has m, you launch an isSameTree from up to n anchor points, and each comparison can cost up to O(m) — O(n·m) worst case. On a long skewed tree where a comparison keeps almost matching before failing at the bottom, you pay for that near-miss over and over.

The key insight: make the tree a string#

A binary tree is fully described by a pre-order traversal — as long as you record the nulls. Write down the node value, then recurse left, then recurse right, emitting a marker every time you hit an empty child. That marked pre-order string is an injective fingerprint: two trees produce the same string if and only if they are the same tree.

Two details make the encoding trustworthy:

• Null markers are mandatory. Without them, [1,2] (a node with a left child) and [1,null,2] (a node with a right child) both serialize to "12" — collision. The null tokens pin down shape.
• A separator before each value prevents digit smearing. Prefix every value with # so 12 reads as one token, not 1 followed by 2. Otherwise a tree with a 12 node could masquerade as a 1/2 pair.

Here's the payoff. Pre-order keeps every subtree's tokens contiguous in the string. So subRoot is a subtree of root exactly when subRoot's serialization appears as a substring of root's serialization. Tree containment becomes substring search.

The optimal solution#

Serialize both trees with the same encoder, then let String.includes do the search:

traverse returns "null" at an empty node, otherwise #value glued to the serialized left subtree and then the serialized right subtree. hash1 is root's fingerprint, hash2 is subRoot's. The final hash1.includes(hash2) asks whether subRoot's contiguous token run sits anywhere inside root's — the whole algorithm in one line.

Walkthrough#

Trace root = [3,4,5,1,2]. The traversal visits nodes in pre-order (node, then left subtree, then right subtree), appending a token at each step.

So hash1 = "#3#4#1nullnull#2nullnull#5nullnull".

Run the same encoder on subRoot = [4,1,2]: visit 4, then 1 (two null children), then 2 (two null children), giving hash2 = "#4#1nullnull#2nullnull".

Now the search. Line up hash2 against hash1:

hash2 appears starting at character index 2 of hash1, so hash1.includes(hash2) is true. The contiguous match is proof that a subtree identical to subRoot lives inside root.

Complexity#

Let n = nodes in root, m = nodes in subRoot. The serialized strings have length proportional to their node counts.

The substring step is where the theory and the JavaScript engine diverge. String.includes in the worst case is O(n·m), the same asymptotic ceiling as brute force. Swap in a linear-time matcher like KMP or a rolling hash and the search drops to O(n + m), making the full solution linear — that's the real reason this reframe is worth knowing. Space is O(n + m) for the two strings, plus O(h) recursion stack where h is the height of root.

Common mistakes#

• Dropping the null markers. #1#2 with no nulls can't tell a left-only tree from a right-only tree. Emit null (or any sentinel) at every empty child or the fingerprint stops being injective.
• Forgetting the value separator. Concatenating raw values lets 12 collide with 1 then 2. The # prefix keeps hash1 = "#12..." from matching a hash2 built from separate 1 and 2 nodes.
• Using in-order instead of pre-order. In-order traversal does not keep subtrees contiguous, so substring containment no longer corresponds to subtree containment. Pre-order (or post-order) is required.
• Assuming includes is linear. It's convenient, not free. If an interviewer pushes on worst-case time, name KMP or Rabin-Karp to get a genuine O(n + m).
• Matching a partial subtree. A subtree includes every descendant. The null markers enforce this automatically — a match that stops early would leave leftover tokens that break contiguity.

Where this pattern shows up next#

The same "equal-tree" machinery, viewed from different angles:

• Subtree of Another Tree — the anchor-and-compare version of this exact problem, without serialization.
• Same Tree — the node-by-node equality check that both approaches lean on.
• Symmetric Tree — mirror-equality, a twist on comparing two structures in lockstep.
• Symmetric Tree - Iterative — the same mirror check done with an explicit queue instead of recursion.

Watch both trees serialize token by token and the substring match light up in the Subtree of Another Tree (Serialization) visualizer.

FAQ#

Why do the null markers matter in tree serialization?#

Without null markers, structurally different trees can produce the same string. A node with only a left child [1,2] and a node with only a right child [1,null,2] both flatten to "12" if you skip the empty slots. Emitting a null token at every missing child makes the encoding injective — the string then uniquely determines the tree, which is the whole premise that lets substring search stand in for subtree comparison.

Why prefix each value with # instead of joining values directly?#

The # is a delimiter that stops adjacent numbers from smearing together. Concatenate 1 and 2 and you get "12", which is indistinguishable from a single node valued 12. Prefixing gives "#1#2" versus "#12" — now the tokens can never be misread, so two different trees can't accidentally share a fingerprint through digit ambiguity.

Is the serialization approach actually faster than brute force?#

With JavaScript's built-in String.includes, both are O(n·m) in the worst case, so the win is conceptual clarity, not raw asymptotics. The real speedup comes from pairing serialization with a linear-time string matcher like KMP or a rolling hash (Rabin-Karp), which brings the substring search down to O(n + m) and makes the whole solution linear — something the anchor-at-every-node brute force can't match.

Can I use pre-order for the serialization, or does it have to be a specific order?#

Pre-order and post-order both work because each keeps every subtree's tokens contiguous in the output string, which is exactly what substring containment needs. In-order does not — its layout interleaves ancestors and descendants in a way that breaks the contiguity, so a subtree's tokens no longer form an unbroken slice. Stick with pre-order (node, left, right) as shown here.

Does this handle duplicate values in the tree?#

Yes. Duplicate values are fine because the fingerprint encodes full structure, not just the multiset of values. Two subtrees with the same numbers but different shapes serialize to different strings thanks to the null markers, so a substring match only fires when both the values and the arrangement line up exactly — which is precisely the definition of an identical subtree.