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,3might 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.
In short: choose an encoding that cannot be misread (null markers, brackets, or an explicit child count) and the parser becomes a single left-to-right pass 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 recursion depth equals the nesting depth, so a long left chain such as 1(2(3(4(...)))) hits Python's default limit of about 1000 frames. The lesson also has an explicit-stack parser: a number creates a node and attaches it to the top of the stack, ( needs no action, and ) pops. It is still O(n) time and O(h) space, but the depth lives in a list instead of the call stack.
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 is an end-of-children sentinel (#) after each child list. It also works, but it writes one # for every node, and the reader must test for it before every child and make sure it cannot collide with a real value. What does not work is omitting both. Either way the output is O(n) and the recursion adds O(h), which is O(n) for a chain, so the recursive reader has the same Python depth problem and the lesson gives an iterative one.
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 time and space in the worst case, because the strings' lengths sum quadratically on a skewed tree. Assigning each distinct subtree an integer id instead (one id per distinct (value, left id, right id) triple) brings it back to O(n) time and O(n) space for the map, plus the O(h) recursion stack, which is O(n) on a skewed tree. Mentioning that trade unprompted is the senior answer.
4. A 30-second worked example (ambiguity)
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.
- 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. The recursive parser fails on very long left chains in Python, so the lesson adds an explicit-stack parser.
Pattern: recursive descent with a shared cursor. Target: O(n) time, O(h) space (recursion stack or explicit stack), plus the O(n) output.
Serialize and Deserialize N-ary Tree
Round-trip a tree with arbitrary arity. Compare an end-of-children sentinel (one # per node) with writing each node's child count, so the parser knows exactly when to stop.
Pattern: arity-encoded preorder. Target: O(n) both ways, plus O(h) recursion stack.
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²) time and space with strings, O(n) time and map space with subtree ids, plus the O(h) recursion stack in both (O(n) on a skewed tree).
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. It is
O(n²)and loses position. - Recursing on a long left chain in Python. Both the string parser and the N-ary reader exceed the default recursion limit; know the explicit-stack versions.
- 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 isO(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
- The encoding is the problem. Ambiguity cannot be parsed away.
- Explicit arity or explicit nulls. An N-ary tree needs one of them; a child count avoids the per-node
#of the sentinel form. - Parse with a shared cursor, never by slicing.
- A canonical serialisation is an identity, which makes subtree comparison a map lookup.
- Report on the second sighting to emit each duplicate once.
- Know the cost of your keys. Strings are quadratic on skewed trees; integer ids are linear.
- 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.
Core idea: Give every subtree a canonical fingerprint: a string built bottom-up as
value,left_fingerprint,right_fingerprint(with explicit markers for empty children). Two subtrees are duplicates exactly when their fingerprints match. Count fingerprints in a hash map and record a node the moment its fingerprint is seen for the second time.
Problem, rephrased
An optimizing compiler hands you the expression tree of a compiled function. Identical sub-expressions (say a*b + c computed in three separate places) show up as structurally identical subtrees, and before emitting machine code you want each repeated sub-expression computed once and its result reused. You're given the root of a binary tree: the expression tree. Node values are integers.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson