Serialize and Fingerprint Subtrees

Serializing a tree means writing it as a flat string that you can turn back into the same tree. Fingerprinting is the same idea used for comparison: give each subtree a description so that equal shapes get equal descriptions. Both come down to a preorder walk that records structure, not just values.

The idea#

A plain preorder list loses the shape: [1, 2] could be a left child or a right child. Writing a marker such as N for every missing child fixes that. With null markers, one preorder traversal is enough to rebuild the tree. Read a token; if it is N return None, otherwise make a node, then build its left subtree, then its right, from the tokens that follow. Each call consumes exactly one token, so the reader never needs to know subtree sizes.

To find duplicate subtrees, you need a description per subtree. There are three ways to build one, and they differ in cost:

Fingerprint	Cost per node	Total
A string such as `(left)val(right)`	builds a string as long as the subtree	$O(n^2)$
A nested tuple `(left_tuple, val, right_tuple)`	hashing walks the whole nested tuple	$O(n^2)$
A triple of integer IDs `(left_id, val, right_id)`	hashes three small values	$O(n)$

Why nested tuples are still $O(n^2)$ #

The tuple row surprises most people, so here is why. Building a nested tuple is cheap, because the outer tuple only stores references. Hashing it is not. Python computes a tuple's hash from the hashes of its elements, and CPython has traditionally not cached tuple hashes. So when the dictionary hashes a grandparent's tuple, it hashes the parent's tuple inside it, then the leaf tuples inside that, and so on all the way down. A dictionary hit also compares the two tuples element by element, just as deep. Either way, the work at a node grows with the size of its subtree. Summed over all nodes, that is $O(n^2)$ for a skewed tree.

The two-map fix#

The fix is to keep every dictionary key flat. Give each distinct shape a small integer ID the first time you see it. Two maps do the work:

A translator, triplet_to_id, turns (left_id, val, right_id) into an ID.
A counter tallies how often each ID appears.

Each call returns an ID, not a structure. The recursion still happens in your code, but every key the dictionary hashes is a flat triple of small values. So hashing is $O(1)$ and the whole walk is $O(n)$ . Two subtrees get the same ID exactly when they have the same value at the root and the same left and right shapes.

How to spot it#

These cues point to serialization or fingerprints.

"Serialize and deserialize", "encode and decode a tree".
"Find duplicate subtrees", "is this tree a subtree of that one", "identical folders".
Any time you want to use a subtree as a dictionary key.

Template#

This is the codec shape: a preorder writer with null markers and a reader that consumes one token per call. Nodes follow LeetCode's TreeNode(val, left, right).

serialize(node):
    if node is None: write "N"; return    # the marker pins down the shape
    write node.val
    serialize(node.left)
    serialize(node.right)

deserialize():                            # tokens and index i are shared
    tok = tokens[i]; i += 1               # every call consumes one token
    if tok is "N": return None
    node = new node with tok
    node.left = deserialize()             # same order as serialize
    node.right = deserialize()
    return node

The fingerprint shape#

The ID version is a postorder walk, because a node's ID depends on its children's IDs. Each call returns a small integer for its subtree's shape.

triplet_to_id = empty map; count = empty counter
fingerprint(node):
    if node is None: return 0             # ID 0 means "empty"
    key = (fingerprint(node.left), node.val, fingerprint(node.right))
    if key is new: triplet_to_id[key] = next unused ID
    shape = triplet_to_id[key]
    count[shape] += 1
    use the count here (for example, report a repeat)
    return shape

Pitfalls#

These mistakes mix up subtrees or repeat answers.

Advancing the index in the wrong place. If the reader doesn't consume exactly one token per call, left and right subtrees read each other's tokens. Advance the index right after reading.
Forgetting the null markers. Preorder without them can't tell a left child from a right child.
Reporting a duplicate more than once. Report a shape the moment its count becomes exactly 2, not every time it is above 1.
Shadowing builtins. Naming a variable id hides Python's id(); pick another name.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first one.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Serialize and Deserialize Binary Tree

Use the codec template with a comma between tokens. Split the string once, and keep the token index local to the call.

Hint: Serialize and Deserialize BST

The general codec works, but it misses the point. A BST's preorder alone fixes the tree, with no null markers. When you rebuild, a value belongs in the current subtree only if it fits the range the ancestors allow. That gives a shorter string.

Hint: Construct String from Binary Tree

Write val(left)(right) and drop the empty brackets you don't need. With no children, write only val. With no right child, drop its (). With no left child but a right child, keep the empty (), or the right child would read as a left child.

Hint: Find Duplicate Subtrees

Use the fingerprint template with integer IDs. Add a node to the answer when its shape's count becomes exactly 2, so each shape appears once.

Hint: Subtree of Another Tree

Fingerprint both trees with one shared triplet_to_id map. subRoot is a subtree of root when its ID matches the ID of some node in root.

Hint: Delete Duplicate Folders in System

Build a tree of folders from the paths. Fingerprint each folder by its sorted child names together with the children's IDs, so identical structures get identical IDs. A non-empty structure seen two or more times marks those folders for deletion, along with everything under them.

Key takeaways#

Null markers make a single preorder traversal enough to rebuild a tree.
When deserializing, each call consumes exactly one token.
Strings and nested tuples as fingerprints cost $O(n^2)$ , because each one is as big as its subtree.
Map each (left_id, val, right_id) triple to an integer ID; flat keys make the walk $O(n)$ .

Core idea#

Serializing writes a tree as a flat string you can turn back into the same tree. Fingerprinting gives equal subtree shapes equal descriptions. Both use a preorder walk that records structure, not only values.

Key points#

A plain preorder list loses the shape. [1, 2] can be a left or a right child.
Write a marker such as N for every missing child. Then one preorder traversal rebuilds the tree.
Deserialize: read one token per call. N returns None. Otherwise build the node, then its left, then its right.
Duplicate subtrees: map each (left_id, val, right_id) triple to a small integer ID.
Use two maps: a translator triplet_to_id and a counter of IDs.
Each call returns an ID. Flat keys hash in $O(1)$ , so the walk is $O(n)$ .
BST: preorder alone fixes the tree with value ranges. No null markers needed.
Bracket string val(left)(right): drop empty () except for a missing left child when a right child exists.

Fingerprint cost#

Fingerprint	Total cost
String `(left)val(right)`	$O(n^2)$
Nested tuple	$O(n^2)$ : hashing and comparing walk the whole tuple
Integer ID triple	$O(n)$

Template#

triplet_to_id = empty map; count = empty counter
fingerprint(node):
    if node is None: return 0             # ID 0 means empty
    key = (fingerprint(node.left), node.val, fingerprint(node.right))
    if key is new: triplet_to_id[key] = next unused ID
    shape = triplet_to_id[key]
    count[shape] += 1
    if count[shape] == 2: report node     # each shape once
    return shape

Pitfalls#

Advancing the token index in the wrong place. Advance right after you read.
No null markers. Preorder cannot tell left from right.
Reporting a duplicate more than once. Add it when the count is exactly 2.
Naming a variable id. It hides Python's id().

Say it in an interview#

"With null markers, one preorder traversal is enough to rebuild the tree."
"Map each subtree to an integer ID, so every key is flat and the walk is O(n)."

The idea#

Why nested tuples are still O(n2)O(n^2)O(n2)#

The two-map fix#

How to spot it#

Template#

The fingerprint shape#

Pitfalls#

Problems in this pattern#

Hints#

Key takeaways#

Core idea#

Key points#

Fingerprint cost#

Template#

Pitfalls#

Say it in an interview#

Why nested tuples are still $O(n^2)$ #