Serialize and Reconstruct

What is this?

Flattening a tree is easy. Flattening it so that exactly one tree can be read back is the problem. Every decision — whether to write null markers, whether to record how many children each node has, where the delimiters go — is a decision about ambiguity, and an encoding that loses information cannot be rescued by a clever parser.

The third problem here turns the same act sideways: if a subtree's serialisation is canonical, then two subtrees are identical exactly when their strings match, so the encoding becomes an equality test.

💡 Fun fact: an N-ary tree cannot be serialised as a bare preorder list. The sequence 1,2,3 might be a root with two children, or a chain of three, and nothing in the string distinguishes them. Writing the child count after each value — 1,2 2,0 3,0 — makes the parse deterministic and single-pass. This is precisely why real formats carry length prefixes: protobuf, DNS messages and TLV encodings all solve the same ambiguity the same way.

🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: choose an encoding that cannot be misread — null markers, brackets, or an explicit child count — and the parser becomes a single left-to-right consumption with no lookahead.

1. Parse with a cursor, not with slicing

Construct Binary Tree from String takes input like "4(2(3)(1))(6(5))": a value, then optionally a bracketed left subtree, then optionally a bracketed right. The natural implementation is a shared cursor consumed as you go:

i = 0
def parse():
    global i
    sign = 1
    if s[i] == '-': sign = -1; i += 1
    start = i
    while i < len(s) and s[i].isdigit(): i += 1
    node = TreeNode(sign * int(s[start:i]))
    if i < len(s) and s[i] == '(':
        i += 1; node.left = parse(); i += 1      # consume '(' … ')'
    if i < len(s) and s[i] == '(':
        i += 1; node.right = parse(); i += 1
    return node

Two details matter. Negative values mean the digit scan must handle a leading -, which is easy to miss when the samples are all positive. And the cursor must be shared, not passed by value — slicing substrings instead is O(n²) and loses the position.

The rule that the first bracketed group is always the left child is what makes the grammar unambiguous: a node with only a right child is impossible to express, and the problem guarantees it never occurs.

2. Encode arity for N-ary trees

serialize:   value, childCount, then each child recursively
deserialize: read value, read count, then read exactly that many children

The count tells the parser precisely when a node's children end, so no sentinel and no lookahead is needed. The alternative — a null marker after each child list — also works; what does not work is omitting both.

3. Serialisation as identity

For Find Duplicate Subtrees, serialise every subtree post-order and count the strings:

def walk(node):
    if not node: return "#"
    key = f"{node.val},{walk(node.left)},{walk(node.right)}"
    count[key] += 1
    if count[key] == 2: result.append(node)     # append on the SECOND sighting only
    return key

Appending on exactly the second occurrence is what stops a subtree appearing three times in the output when it occurs three times in the tree. And the # for null is essential — without it, a left-only and a right-only child serialise identically.

Worth stating: building a string per subtree makes this O(n²) in the worst case, because the strings' lengths sum quadratically on a skewed tree. Assigning each distinct subtree an integer id instead brings it back to O(n), and mentioning that trade unprompted is the senior answer.

4. A 30-second worked example (ambiguity)

N-ary preorder without arity:   1, 2, 3

   could be:      1              or:      1
                 / \                      |
                2   3                     2
                                          |
                                          3

with child counts:  1,2  2,0  3,0   →  only the first tree
                    1,1  2,1  3,0   →  only the second

The bare list is one string describing two trees; the annotated list describes exactly one. That is the entire content of "choose an unambiguous encoding".

5. Where you'll actually meet this

• Wire formats. Length-prefixed encodings — protobuf, TLV, DNS — exist to solve this exact ambiguity.
• Compilers. Common-subexpression elimination hashes canonical subtree forms to find repeated computation.
• Caching and memoisation. Structural keys let identical subproblems share a cache entry.
• Version control and diffing. Detecting moved or duplicated subtrees between revisions.
• Document and config parsing. Bracketed nested formats are parsed with exactly this cursor discipline.

6. Problems in this chapter

▶ Construct Binary Tree from String

Rebuild a tree from "4(2(3)(1))(6(5))". A shared cursor, digit scanning with sign handling, and the rule that the first bracket is the left child.
Pattern: recursive descent with a shared cursor. Target: O(n) time, O(h) space.

▶ Serialize and Deserialize N-ary Tree

Round-trip a tree with arbitrary arity. Write each node's child count so the parser knows exactly when to stop.
Pattern: arity-encoded preorder. Target: O(n) both ways.

▶ Find Duplicate Subtrees

Every subtree occurring more than once. Serialise each subtree canonically and count; report on the second sighting.
Pattern: serialisation as a hash key. Target: O(n²) with strings, O(n) with subtree ids.

7. Common pitfalls 🚫

• Omitting null markers. A left-only child and a right-only child serialise identically without them.
• Serialising an N-ary tree without arity. The result cannot be parsed back at all.
• Slicing substrings while parsing instead of advancing a shared cursor — O(n²) and it loses position.
• Not handling negative values in the digit scan.
• Appending on every occurrence in the duplicate search, which emits a subtree once per repetition.
• Claiming O(n) for the string-keyed version. It is O(n²) on a skewed tree; the id-based variant is the linear one.
• Assuming the first bracket could be a right child. The grammar forbids it, and relying on that should be stated rather than assumed silently.

8. Key takeaways

1. The encoding is the problem. Ambiguity cannot be parsed away.
2. Explicit arity or explicit nulls — an N-ary tree needs one of them.
3. Parse with a shared cursor, never by slicing.
4. A canonical serialisation is an identity, which makes subtree comparison a map lookup.
5. Report on the second sighting to emit each duplicate once.
6. Know the cost of your keys. Strings are quadratic on skewed trees; integer ids are linear.
7. Why interviewers like it: the traversal is trivial and the format decisions are everything, which makes it a direct test of how carefully you reason about representation.

Order: Construct Binary Tree from String → Serialize and Deserialize N-ary Tree → Find Duplicate Subtrees.