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

You are looking at this pattern when…

• “Same tree”, “identical”, “mirror”, or “symmetric” — 100, 101, 951.
• “Is A a subtree of B” — 572, 1367.
• Serialize and deserialize — 297, 449, 428.
• Find duplicate subtrees — 652, where serialisation becomes a hash key.
• Merge or combine two trees position by position — 617.
• You need to compare two trees in any way. That is a parallel recursion over both at once.

Visual intuition

Serialisation is pre-order with the nulls written down. Watch the output strip: the trace below emits a token per node in exactly the order serialize appends them, and every gap in the tree is where a # belongs.

treePre-order is the serialisation order — the nulls are what you must addLC 297 · O(n) time and space

call stack

1

1def preorder(node, out):2    if node is None:3        return4    out.append(node.val)      # visit5    preorder(node.left, out)6    preorder(node.right, out)7    out.append(node.val)      # visit

node1stack depth1

enterEnter 1. The recursive call is pushed onto the stack, which is now 1 frame deep.

Play‹›1/16⟲

This trace emits 1, 2, 3, 4, 5. Node 2's two empty children are visited by the real algorithm and produce '#,#' -- which is precisely the information that makes 1,2,#,#,3,4,#,#,5,#,# reconstructible while a bare '1,2,3,4,5' is not. Deserialisation replays this same order, consuming one token per step.

The reason the marker matters is a two-tree ambiguity: without nulls, pre-order [1, 2] is produced both by 2 as a left child and by 2 as a right child. With them, 1,2,#,#,# and 1,#,2,#,# are different strings.

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))

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

The guard order matters

if not p and not q must come first. If you test p.val != q.val before confirming both exist, you dereference None and get an AttributeError the moment one tree is shorter than the other.

The three guards, in order, are exactly the three cases: both empty (equal), exactly one empty or values differ (not equal), otherwise recurse. Test with p = [1,2] and q = [1,null,2] — same values, different shape, must be False.

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()

Why null markers are mandatory

Without them, preorder [1, 2] is produced by two different trees — 2 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,#,#,# and 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, so a character-by-character parse would break.

The iter(...) plus 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.

Dry run

Serialisation of [1,2,3,null,null,4,5]. The tree is

text

    1
   / \
  2   3
     / \
    4   5

Pre-order, appending # for every empty child:

visit	emits	tokens so far
1	1	1
2	2	1,2
2.left = None	#	1,2,#
2.right = None	#	1,2,#,#
3	3	1,2,#,#,3
4	4, then two #	1,2,#,#,3,4,#,#
5	5, then two #	1,2,#,#,3,4,#,#,5,#,#

Result: 1,2,#,#,3,4,#,#,5,#,#. 11 tokens for 5 nodes — an $n$-node binary tree has exactly $n + 1$ empty child slots, so the output is always $2n + 1$ tokens. That is the honest space answer, and it is why serialisation is $O(n)$ and not somehow smaller.

Deserialisation replays the same order: next(tokens) yields 1, recurse left → 2, recurse left → # → None, recurse right → # → None, unwind, recurse right of 1 → 3, and so on. No index arithmetic, because the iterator is the position.

Why the markers are not optional. Two different trees, same values:

tree	serialisation
[1,2] (2 is a left child)	1,2,#,#,#
[1,null,2] (2 is a right child)	1,#,2,#,#

Distinguishable. Drop the #s and both become 1,2.

Structural equality on that same pair — is_same_tree([1,2], [1,null,2]):

depth	comparison	result
0	1 == 1	recurse both sides
1	p.left = 2 vs q.left = None	False — one empty, one not

Correctly False: same values, different shape. And note what would happen with the guards in the wrong order — testing p.val != q.val before confirming both nodes exist dereferences None and raises AttributeError on this very input.

The subtree shortcut, on LC 572’s example root = [3,4,5,1,2], subRoot = [4,1,2]:

text

root    -> 3,4,1,#,#,2,#,#,5,#,#
subRoot ->   4,1,#,#,2,#,#

Wrapping both in commas, ",4,1,#,#,2,#,#," is a substring of ",3,4,1,#,#,2,#,#,5,#,#," → True. The two safeguards are what make that trustworthy: the commas stop 2 matching inside 12, and the #s stop a pattern matching a node that has extra children below it.

Complexity

Task	Time	Space
Same tree	$O(\min(n, m))$	$O(h)$
Serialize / deserialize	$O(n)$ — exactly $2n + 1$ tokens	$O(n)$
Subtree, naive (same() at every node)	$O(n \cdot m)$	$O(h)$
Subtree, via serialisation + substring	$O(n + m)$	$O(n + m)$
Duplicate subtrees (LC 652)	$O(n)$ average with hashing	$O(n)$

$O(\min(n, m))$ for equality is worth saying precisely: the recursion stops at the first mismatch, so it is bounded by the smaller tree — it can never walk past the point where one tree runs out.

The naive subtree solution is $O(n \cdot m)$ and passes LeetCode’s constraints comfortably. Offer the serialisation shortcut as the asymptotic improvement, but only with both safeguards named — an interviewer who has seen the [12] / [2] failure will ask.

The subtree trap

LC 572 asks whether subRoot appears as a subtree of root. The natural solution tries 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))

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

Substring containment is not subtree containment

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

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

Two fixes, both needed:

1. Delimit every value, so tokens cannot merge: ",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 root that has extra children below it.

With both, "^,12,#,#" versus ",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

The == 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 left against right	101 · 951
Subtree containment	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 True if they are structurally identical and every corresponding node has the same value.

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

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

pch.exerciseTag pch.exerciseTitle

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]) gives False — identical multisets of values, different shape. This is why “compare sorted values” is not a valid solution.
• ([1,2,1], [1,1,2]) gives False — same shape, values in different positions.
• ([], []) gives True — two empty trees are equal.
• ([1], []) gives False — 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.left with q.right and p.right with q.left. “Iteratively?” — push pairs onto a stack and compare as you pop. “Compare k 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 root and subRoot, return True if subRoot appears as a subtree of root. A subtree consists of a node in root and all of that node’s descendants.

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

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

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Try an exact match at every node of root. same 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: same is called at up to n 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 4 in root has children 1 and 2, but 1 has an extra child 0. The values along the top match subRoot exactly, yet the subtree is different — so same must (and does) fail when it reaches 1’s children and finds 0 where subRoot has None.

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

The $O(n + m)$ solution, done correctly

Serialise both trees with delimiters and null markers, then ask whether serialize(root) contains 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)

The leading comma before every value prevents 12 from matching 2, and the # markers prevent a partial match. Substring search is $O(n + m)$ with KMP (Python’s in 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^4, -1000 <= Node.val <= 1000.

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

Why this test round-trips instead of checking the string

The format is yours to choose, so there is no single correct output string. The test serialises then deserialises and compares the resulting tree against the original in level-order form — which is exactly the property the problem requires.

pch.exerciseTag pch.exerciseTitle

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), so the string must be tokenised, not read character by character.
• iter plus next. 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) produces "#", and deserialising "#" returns None. The round trip works with no special case — worth checking, since [] is a legal input.

[1,2] versus [1,null,2] are the pair that prove the markers are doing their job: they serialise to 1,2,#,#,# and 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,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

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

LC 449 versus LC 297 — what the extra structure buys you

For a general binary tree you need null markers, because [1,2] is ambiguous. For a BST you do not: the ordering tells you which values belong in which subtree, so serialize is just the preorder and deserialize recurses with (low, high) bounds — the same technique as building a BST from preorder.

That is a genuinely smaller string, and noticing that a BST’s constraint replaces the markers is exactly the kind of observation these two problems are paired to elicit.

7 problems

4 easy2 medium1 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

AllEasyMediumHard

Unsolved onlyExportImportReset

• ○100Same TreeeasyThree guards in order; shape matters as much as valuesNeetCode 150Blind 75LeetCode Top Interview 150
• ○101Symmetric TreeeasyCompare `left` against `right` -- mirrored recursionLeetCode Top Interview 150
• ○572Subtree of Another Treeeasy`same()` at every node; the string shortcut needs delimiters **and** markersNeetCode 150Blind 75
• ○617Merge Two Binary TreeseasyParallel recursion that builds a third tree
• ○449Serialize and Deserialize BSTmediumA BST needs **no** markers -- preorder alone determines it
• ○652Find Duplicate SubtreesmediumSerialisation as a hash key; report on count `== 2`
• ○297Serialize and Deserialize Binary TreehardPreorder + null markers is self-delimitingNeetCode 150Blind 75metaamazongooglebloomberg

Interview follow-ups

They ask	What they’re checking	The answer
“Why null markers?”	Foundations	Without them preorder is ambiguous — [1,2] fits two trees. With them, one traversal determines the tree
“Why is substring containment wrong for subtrees?”	Depth	"12" contains "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 isSameTree?”	Care	Both-None first, or you dereference None 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 — True for LC 100; serialize(None) must round-trip.
• One tree empty — False; the guard-order test.
• Same values, different shape — [1,2] vs [1,null,2]; the reason shape must be compared.
• Same shape, values transposed — [1,2,1] vs [1,1,2].
• Subtree matching at a non-root node — root = [1,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] vs [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.

Self-check

pch.quizTag Serialise, compare and subtree — self-check

1. Why does serialisation need explicit null markers when reconstruction from two traversals does not?

   A To make the string shorter B Because a bare pre-order is ambiguous — `[1,2]` is produced both by 2 as a left child and by 2 as a right child; the markers make pre-order alone determine the tree, which is what a second traversal would otherwise supply C Because values can be negative D They are optional in both cases
   pch.quizShowAnswer

   B — Because a bare pre-order is ambiguous — `[1,2]` is produced both by 2 as a left child and by 2 as a right child; the markers make pre-order alone determine the tree, which is what a second traversal would otherwise supply — With markers the two trees serialise to 1,2,#,#,# and 1,#,2,#,#. That is the same ambiguity the Tree Construction page fixes with an in-order array — two different remedies for one problem.

2. In `is_same_tree`, why must `if not p and not q` come before the value comparison?

   A Style only B Because comparing p.val before confirming both nodes exist dereferences None and raises AttributeError the moment one tree is shorter C Because both-empty is the common case D To allow duplicate values
   pch.quizShowAnswer

   B — Because comparing p.val before confirming both nodes exist dereferences None and raises AttributeError the moment one tree is shorter — The three guards are the three cases in order: both empty (equal), exactly one empty or values differ (not equal), otherwise recurse. Testing [1,2] against [1,null,2] exercises exactly this.

3. How many tokens does serialising an n-node binary tree with null markers produce?

   A n B 2n + 1 — an n-node binary tree has exactly n + 1 empty child slots, and each becomes a marker C n log n D It depends on the shape
   pch.quizShowAnswer

   B — 2n + 1 — an n-node binary tree has exactly n + 1 empty child slots, and each becomes a marker — Independent of shape, which is a nice thing to be able to state. The dry run's 5-node tree produces 11 tokens.

4. Serialise both trees and ask whether one string contains the other. What breaks, and what fixes it?

   A Nothing breaks B `root = [12]`, `subRoot = [2]`: "12" contains "2". Both fixes are needed — delimit every value with commas so tokens cannot merge, and include null markers so a partial match cannot succeed C Only negative values break it D It needs the trees to be the same height
   pch.quizShowAnswer

   B — `root = [12]`, `subRoot = [2]`: "12" contains "2". Both fixes are needed — delimit every value with commas so tokens cannot merge, and include null markers so a partial match cannot succeed — Commas alone stop the digit-overlap failure; markers alone stop a pattern matching a node that has extra descendants. The general lesson: when flattening a structure into text, ask what two different structures could flatten to overlapping strings.

5. What is the complexity of the naive LC 572 solution, and should you use it?

   A O(n + m); yes B O(n · m) — and yes, it passes LeetCode's constraints; offer the O(n + m) serialisation shortcut as an improvement, but only with both safeguards named C O(n²) always; no D O(n log n); no
   pch.quizShowAnswer

   B — O(n · m) — and yes, it passes LeetCode's constraints; offer the O(n + m) serialisation shortcut as an improvement, but only with both safeguards named — Calling same() at every node is the honest first answer. Leading with the string shortcut and then being shown the [12]/[2] counter-example is a much worse position to be in.

6. Why is `iter(...)` + `next(...)` the right idiom for deserialisation?

   A It is faster than indexing B Because the recursion consumes tokens in exactly the order serialisation produced them, so a stateful 'give me the next token' removes all index arithmetic C Because the tokens are unordered D Because it handles the null markers automatically
   pch.quizShowAnswer

   B — Because the recursion consumes tokens in exactly the order serialisation produced them, so a stateful 'give me the next token' removes all index arithmetic — The iterator IS the position. Threading an index through the recursion works but invites off-by-one bugs, and passing an integer by value would not even propagate the advance.

Recall card

• Cue — comparing two trees, encoding a tree as a string, or asking whether one tree appears inside another.
• Equality — three guards in order: both empty → True; one empty or values differ → False; else recurse both sides. $O(\min(n, m))$.
• Serialisation — pre-order plus a # for every empty child, comma-separated. Exactly $2n + 1$ tokens, regardless of shape.
• Deserialisation — tokens = iter(data.split(",")) and consume with next(), in the same order; the iterator is the position.
• Markers are mandatory — without them [1,2] and [1,null,2] are the same string.
• Subtree — naive same() at every node is $O(n\cdot m)$ and is fine. The $O(n+m)$ substring trick needs comma delimiters (so 2 does not match inside 12) and null markers (so a partial match cannot succeed).
• Serialisation as a hash key — the $O(n)$ route to LC 652 (duplicate subtrees): count each subtree’s serialisation in a dictionary.

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.
• iter plus next 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] versus [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.