Serialize Compare and Subtree

Two trees are the same when they have the same shape and the same values in the same places. That is a stricter condition than “the same set of values”, and getting the distinction right is what this family of problems tests.

The recursion is short. What makes these problems interesting is the bookkeeping:

Null markers. A traversal that omits empty children is ambiguous, so serialisation must record them explicitly.
Structural comparison. Comparing values without comparing shape accepts trees that are genuinely different.
Substring is not subtree. The tempting “serialise both and check containment” shortcut is wrong unless you add delimiters — and knowing why is the point of LC 572.

What you’ll learn

The parallel recursion for structural equality, and the order of its guards.
Why serialisation needs explicit null markers, with a concrete counter-example.
The subtree-matching trap, and how to fix the string shortcut.
Using serialisation as a hash key to find duplicate subtrees in $O(n)$ .
Three real LeetCode problems solved in the browser: 100, 572, 297.

The cue

Template 1 — structural equality

is_same_tree.py

def is_same_tree(p, q):
    if not p and not q:
        return True                    # both empty -> equal
    if not p or not q or p.val != q.val:
        return False                   # one empty, or values differ
    return (is_same_tree(p.left, q.left)
            and is_same_tree(p.right, q.right))

is_same_tree.py

def is_same_tree(p, q):
    if not p and not q:
        return True                    # both empty -> equal
    if not p or not q or p.val != q.val:
        return False                   # one empty, or values differ
    return (is_same_tree(p.left, q.left)
            and is_same_tree(p.right, q.right))

$O(\min(n, m))$ time — it stops at the first mismatch — and $O(h)$ space.

Template 2 — serialisation with null markers

serialize.py

def serialize(root):
    out = []
 
    def dfs(node):
        if not node:
            out.append("#")            # EXPLICIT null marker
            return
        out.append(str(node.val))
        dfs(node.left)
        dfs(node.right)
 
    dfs(root)
    return ",".join(out)
 
 
def deserialize(data):
    tokens = iter(data.split(","))     # an iterator gives us "consume next"
 
    def dfs():
        token = next(tokens)
        if token == "#":
            return None
        node = TreeNode(int(token))
        node.left = dfs()              # the SAME order as serialisation
        node.right = dfs()
        return node
 
    return dfs()

serialize.py

def serialize(root):
    out = []
 
    def dfs(node):
        if not node:
            out.append("#")            # EXPLICIT null marker
            return
        out.append(str(node.val))
        dfs(node.left)
        dfs(node.right)
 
    dfs(root)
    return ",".join(out)
 
 
def deserialize(data):
    tokens = iter(data.split(","))     # an iterator gives us "consume next"
 
    def dfs():
        token = next(tokens)
        if token == "#":
            return None
        node = TreeNode(int(token))
        node.left = dfs()              # the SAME order as serialisation
        node.right = dfs()
        return node
 
    return dfs()

Without them, preorder [1, 2][1, 2] is produced by two different trees — 22 as a left child or as a right child. That is the same ambiguity as in Tree Construction, where the fix was supplying a second traversal.

Markers fix it differently, and better for serialisation: 1,2,#,#,#1,2,#,#,# and 1,#,2,#,#1,#,2,#,# are distinguishable, so preorder plus null markers alone determines the tree. That is why serialisation needs only one traversal where reconstruction from bare traversals needed two.

The marker must be a token that cannot collide with a real value. "#""#" is safe here because values are integers. Also note that separating with ",""," and splitting on it is what makes multi-digit and negative values work — LC 297 allows values down to -1000-1000, so a character-by-character parse would break.

The iter(...)iter(...) plus next(...)next(...) idiom is the neat part of deserialisation: it gives you a stateful “consume the next token” without threading an index through the recursion. The recursion consumes tokens in exactly the order serialisation produced them, so no position arithmetic is needed at all.

	Time	Space
Same tree	$O(\min(n, m))$	$O(h)$
Serialize / deserialize	$O(n)$	$O(n)$
Subtree, naive	$O(n \cdot m)$	$O(h)$
Subtree, via serialisation	$O(n + m)$	$O(n + m)$
Duplicate subtrees	$O(n)$ average with hashing	$O(n)$

The subtree trap

LC 572 asks whether subRootsubRoot appears as a subtree of rootroot. The natural solution tries same()same() at every node:

is_subtree.py

def is_subtree(root, sub_root):
    if not sub_root:
        return True
    if not root:
        return False
    return (same(root, sub_root)
            or is_subtree(root.left, sub_root)
            or is_subtree(root.right, sub_root))

is_subtree.py

def is_subtree(root, sub_root):
    if not sub_root:
        return True
    if not root:
        return False
    return (same(root, sub_root)
            or is_subtree(root.left, sub_root)
            or is_subtree(root.right, sub_root))

$O(n \cdot m)$ — fine at LeetCode’s constraints. But the tempting $O(n + m)$ shortcut hides a real bug:

The idea is to serialise both trees and ask whether one string contains the other. It fails without care.

Take root = [12]root = [12] and subRoot = [2]subRoot = [2]. Serialised naively as values only, "12""12" contains "2""2" — so the shortcut says yes, when [2][2] is not a subtree of [12][12] at all.

Two fixes, both needed:

Delimit every value, so tokens cannot merge: ",12,"",12," does not contain ",2,"",2,".
Include null markers, so a partial match cannot succeed. Without them, a subtree pattern could match a node in rootroot that has extra children below it.

With both, "^,12,#,#""^,12,#,#" versus ",2,#,#"",2,#,#" compares correctly. The lesson generalises: whenever you flatten a structure into a string for comparison, ask what two different structures could flatten to overlapping text.

Serialisation as a hash key

Once a subtree has a canonical string, duplicate detection becomes a dictionary lookup. That is LC 652:

duplicate_subtrees.py

from collections import defaultdict
 
 
def find_duplicate_subtrees(root):
    counts = defaultdict(int)
    out = []
 
    def serialize(node):
        if not node:
            return "#"
        key = f"{node.val},{serialize(node.left)},{serialize(node.right)}"
        counts[key] += 1
        if counts[key] == 2:           # exactly 2 -> report once
            out.append(node)
        return key
 
    serialize(root)
    return out

duplicate_subtrees.py

from collections import defaultdict
 
 
def find_duplicate_subtrees(root):
    counts = defaultdict(int)
    out = []
 
    def serialize(node):
        if not node:
            return "#"
        key = f"{node.val},{serialize(node.left)},{serialize(node.right)}"
        counts[key] += 1
        if counts[key] == 2:           # exactly 2 -> report once
            out.append(node)
        return key
 
    serialize(root)
    return out

The == 2== 2 check reports each duplicate exactly once, however many copies exist. Note that building strings this way is $O(n^2)$ in the worst case because each key contains its children’s keys; assigning integer ids to distinct subtrees instead makes it a true $O(n)$ — worth mentioning if pushed.

The variant map

Variant	The technique	Canonical problem
Identical trees	Parallel recursion, three guards	100
Mirror / symmetric	Compare `leftleft` against `rightright`	101 · 951
Subtree containment	`same()same()` at every node, or delimited serialisation	572
Serialize / deserialize	Preorder + null markers + a token iterator	297
Duplicate subtrees	Serialisation as a hash key	652
Merge two trees	Parallel recursion building a new node	617
Leaf sequence equality	Serialise only the leaves	872

Practice — real LeetCode problems

LC 100 — Same Tree · Easy

Problem. Given the roots of two binary trees, return TrueTrue if they are structurally identical and every corresponding node has the same value.

Constraints. 0 <= number of nodes <= 1000 <= number of nodes <= 100, -10^4 <= Node.val <= 10^4-10^4 <= Node.val <= 10^4.

Examples. [1,2,3][1,2,3] and [1,2,3][1,2,3] give TrueTrue · [1,2][1,2] and [1,null,2][1,null,2] give FalseFalse (same values, different shape) · [1,2,1][1,2,1] and [1,1,2][1,1,2] give FalseFalse

Editorial — approach, complexity, follow-ups

Walk both trees together. At each step there are exactly three possibilities, and the code enumerates them in a safe order.

Time $O(\min(n, m))$ — short-circuits at the first difference. Space $O(h)$ .

The test cases isolate the distinct failure modes:

([1,2], [1,null,2])([1,2], [1,null,2]) gives FalseFalse — identical multisets of values, different shape. This is why “compare sorted values” is not a valid solution.
([1,2,1], [1,1,2])([1,2,1], [1,1,2]) gives FalseFalse — same shape, values in different positions.
([], [])([], []) gives TrueTrue — two empty trees are equal.
([1], [])([1], []) gives FalseFalse — the guard that would crash if ordered wrong.

Follow-ups you should expect: “Check if one is the mirror of the other (LC 101)?” — compare p.leftp.left with q.rightq.right and p.rightp.right with q.leftq.left. “Iteratively?” — push pairs onto a stack and compare as you pop. “Compare kk trees?” — pairwise against the first. “What if node values were floats?” — exact equality becomes unsafe; you would need a tolerance.

LC 572 — Subtree of Another Tree · Easy

Problem. Given the roots rootroot and subRootsubRoot, return TrueTrue if subRootsubRoot appears as a subtree of rootroot. A subtree consists of a node in rootroot and all of that node’s descendants.

Constraints. 1 <= root nodes <= 20001 <= root nodes <= 2000, 1 <= subRoot nodes <= 10001 <= subRoot nodes <= 1000, -10^4 <= Node.val <= 10^4-10^4 <= Node.val <= 10^4.

Examples. root = [3,4,5,1,2]root = [3,4,5,1,2], subRoot = [4,1,2]subRoot = [4,1,2] gives TrueTrue · root = [3,4,5,1,2,null,null,null,null,0]root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]subRoot = [4,1,2] gives FalseFalse (node 44’s subtree has an extra node 00)

Editorial — approach, complexity, follow-ups

Try an exact match at every node of rootroot. samesame requires the two trees to agree completely, all the way down — which is what enforces “and all of that node’s descendants”.

Time $O(n \cdot m)$ worst case: samesame is called at up to nn nodes and costs up to $O(m)$ each. At the given constraints (2000 × 1000) that is acceptable, and it is the expected solution despite the problem’s “Easy” label. Space $O(h)$ .

Case 2 is the whole problem. Node 44 in rootroot has children 11 and 22, but 11 has an extra child 00. The values along the top match subRootsubRoot exactly, yet the subtree is different — so samesame must (and does) fail when it reaches 11’s children and finds 00 where subRootsubRoot has NoneNone.

Case 3, root = [1,1]root = [1,1] and subRoot = [1]subRoot = [1], is also instructive: the match succeeds at rootroot’s left child (a leaf 11), not at the root itself (whose subtree is [1,1][1,1]). It confirms you are trying every node.

Serialise both trees with delimiters and null markers, then ask whether serialize(root)serialize(root) contains serialize(subRoot)serialize(subRoot):

python

def encode(node):
    if not node:
        return ",#"
    return f",{node.val}{encode(node.left)}{encode(node.right)}"
 
return encode(subRoot) in encode(root)

python

def encode(node):
    if not node:
        return ",#"
    return f",{node.val}{encode(node.left)}{encode(node.right)}"
 
return encode(subRoot) in encode(root)

The leading comma before every value prevents 1212 from matching 22, and the ## markers prevent a partial match. Substring search is $O(n + m)$ with KMP (Python’s inin is fast in practice).

Offer this as the optimisation, but be able to explain both guards — an interviewer who asks for it is usually checking whether you know why the naive version is unsound.

Follow-ups you should expect: “Make it $O(n + m)$ ” — as above. “What if you only needed a matching subgraph, not a full subtree?” — a much harder tree pattern-matching problem. “Count occurrences instead?” — tally the matches rather than short-circuiting. “Duplicate subtrees within one tree (LC 652)?” — serialisation as a hash key.

LC 297 — Serialize and Deserialize Binary Tree · Hard

Problem. Design an algorithm to serialise a binary tree to a string and deserialise that string back to the identical tree. The format is up to you.

Constraints. 0 <= number of nodes <= 10^40 <= number of nodes <= 10^4, -1000 <= Node.val <= 1000-1000 <= Node.val <= 1000.

Example. [1,2,3,null,null,4,5][1,2,3,null,null,4,5] must round-trip back to the same tree.

Editorial — approach, complexity, follow-ups

Preorder with explicit null markers is self-delimiting: the recursion always knows when a subtree ends, because it hits a ##. So a single traversal suffices, unlike bare-traversal reconstruction which needs two.

Time $O(n)$ both ways. Space $O(n)$ .

Three details worth stating:

Comma separation. Values can be multi-digit and negative (-1000 <= val <= 1000-1000 <= val <= 1000), so the string must be tokenised, not read character by character.
iteriter plus nextnext. This is what makes deserialisation clean. The recursion consumes tokens in the same order they were produced, so there is no index to thread through or mutate.
The empty tree. serialize(None)serialize(None) produces "#""#", and deserialising "#""#" returns NoneNone. The round trip works with no special case — worth checking, since [][] is a legal input.

[1,2][1,2] versus [1,null,2][1,null,2] are the pair that prove the markers are doing their job: they serialise to 1,2,#,#,#1,2,#,#,# and 1,#,2,#,#1,#,2,#,# respectively.

Follow-ups you should expect:

“Make it more compact.” For a BST (LC 449) you can drop the markers entirely — preorder alone determines a BST, so 1,2,31,2,3 suffices. That is a real saving and shows you noticed the extra structure.
“Use BFS instead.” Level-order with markers works too, and matches LeetCode’s own display format. Equally valid; preorder is usually shorter to write.
“What if values were strings that might contain commas?” You need escaping, or a length-prefixed format. A good practical question.
” $O(1)$ space?” Not possible — the output alone is $O(n)$ .
“Deep trees?” A 10^4-node chain exceeds Python’s recursion limit; raise it or serialise iteratively.

LeetCode problem set

#	Problem	Difficulty	The twist
100	Same Tree	Easy	Three guards in order; shape matters as much as values
101	Symmetric Tree	Easy	Compare `leftleft` against `rightright` — mirrored recursion
572	Subtree of Another Tree	Easy	`same()same()` at every node; the string shortcut needs delimiters and markers
617	Merge Two Binary Trees	Easy	Parallel recursion that builds a third tree
652	Find Duplicate Subtrees	Medium	Serialisation as a hash key; report on count `== 2== 2`
297	Serialize and Deserialize Binary Tree	Hard	Preorder + null markers is self-delimiting
449	Serialize and Deserialize BST	Medium	A BST needs no markers — preorder alone determines it

Interview follow-ups

They ask	What they’re checking	The answer
“Why null markers?”	Foundations	Without them preorder is ambiguous — `[1,2][1,2]` fits two trees. With them, one traversal determines the tree
“Why is substring containment wrong for subtrees?”	Depth	`"12""12"` contains `"2""2"`; you need per-value delimiters and null markers to block partial matches
“What’s the complexity of your subtree solution?”	Precision	$O(n \cdot m)$ naive; $O(n + m)$ with delimited serialisation and substring search
“Compact the serialisation”	Using structure	For a BST, drop the markers — preorder alone suffices (LC 449)
“Guard order in `isSameTreeisSameTree`?”	Care	Both-`NoneNone` first, or you dereference `NoneNone` when the trees differ in size
“Find duplicate subtrees efficiently”	Composition	Serialise each subtree as a hash key; assign integer ids for a true $O(n)$
“Values could contain your delimiter”	Practical robustness	Escape them, or use a length-prefixed encoding

Edge-case checklist

Both trees empty — TrueTrue for LC 100; serialize(None)serialize(None) must round-trip.
One tree empty — FalseFalse; the guard-order test.
Same values, different shape — [1,2][1,2] vs [1,null,2][1,null,2]; the reason shape must be compared.
Same shape, values transposed — [1,2,1][1,2,1] vs [1,1,2][1,1,2].
Subtree matching at a non-root node — root = [1,1]root = [1,1], subRoot = [1]subRoot = [1].
Extra descendants below a match — LC 572 case 2; a subtree must take all descendants.
Single-value trees with digit overlap — [12][12] vs [2][2]; the string shortcut’s counter-example.
Negative and multi-digit values — comma separation is required.
Deep chain — 10^4 nodes exceeds Python’s recursion limit.

Recap

Tree equality is about shape and values together. Compare with a parallel recursion, and order the guards: both empty, then mismatch, then recurse.
Serialisation needs explicit null markers. With them, preorder alone determines the tree; without them it is ambiguous. Separate tokens with a delimiter so multi-digit and negative values survive.
iteriter plus nextnext makes deserialisation index-free — the recursion consumes tokens in the order they were written.
Substring is not subtree. The $O(n+m)$ shortcut needs both per-value delimiters and null markers; [12][12] versus [2][2] is the counter-example.
A subtree includes all descendants — partial matches must fail.
Once subtrees have canonical strings, duplicate detection is a dictionary lookup (LC 652).
A BST needs no markers, because its ordering already encodes the split (LC 449).

Next: the recursion and backtracking patterns — subsets, permutations, and constrained search.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Serialize Compare and Subtree

What you’ll learn

The cue

Template 1 — structural equality

Template 2 — serialisation with null markers

The subtree trap

Serialisation as a hash key

The variant map

Practice — real LeetCode problems

LC 100 — Same Tree · Easy

LC 572 — Subtree of Another Tree · Easy

LC 297 — Serialize and Deserialize Binary Tree · Hard

LeetCode problem set

Interview follow-ups

Edge-case checklist

Recap

Was this page helpful?