</> MAANG.io

Advanced

Advanced problems where modelling is the hard part: implicit graphs, tricky DP states, intervals and design challenges.

0 of 95 solved 0%

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.

Choosing an encoding: null markers, child counts, or canonical strings

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.


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)

N-ary preorder 1,2,3 is ambiguous until child counts fix the tree

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 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; a child count avoids the per-node # of the sentinel form.
  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.

Construct Binary Tree from String

Core idea: The string "4(2(3)(1))(6(5))" is a tree written down, and it follows a tiny grammar: a number, then an optional (left-subtree), then an optional (right-subtree), where each subtree is itself a string in the same grammar. So the parser should mirror the grammar: read the (possibly negative, multi-digit) integer to make the current node; if the next char is (, consume it, recurse to build the left child, and consume the matching ); if another ( follows, recurse again for the right child. The only state shared across the recursion is one index pointer into the string that every call advances. Each character is read once, so the whole parse is O(n). The two traps are local: parse the whole number (a leading - and several digits), and treat both parenthesis groups as optional.


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

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.