Why must a binary tree's preorder serialization include explicit null markers to be decodable?

## What a serialization actually has to pin down A binary tree is two things at once: a **shape** (which nodes exist and how they hang off each other) and a **labelling** (what key sits at each position). A traversal by itself only reports the labels in a particular visiting order. Reconstruction needs the shape too, and that is exactly the part a bare value sequence throws away. ### The ambiguity, concretely Preorder means: emit the node, then the whole left subtree, then the whole right subtree. Consider three different three-node trees: ``` 1 1 1 / / / \ 2 2 2 3 / \ 3 3 ``` All three emit `1 2 3`. The decoder receiving `1 2 3` has no way to place the `3`: left-left, left-right, and right-of-root are all consistent. The number of distinct shapes on n nodes grows like the Catalan numbers, while there is only one value sequence, so ambiguity is not an edge case — it is the normal situation. ### The marker encoding Fix it by making the *absent* children visible. Serialize recursively: if the node is empty, emit a marker token (often written `#`); otherwise emit the key, then serialize left, then serialize right. The same three trees now separate cleanly: ``` 1 2 3 # # # # (left-left chain) 1 2 # 3 # # # (left, then its right child) 1 2 # # 3 # # (two children of the root) ``` **Why the length is 2n+1.** Every node owns two child slots, so a tree of n nodes has 2n slots. Every node except the root fills exactly one slot, so n-1 slots are filled and 2n-(n-1) = n+1 are empty. The stream carries n keys plus n+1 markers. ### Why decoding is one pass The decoder never has to scan ahead to find where the left subtree ends. It keeps a cursor over the token stream and calls itself: ``` build(): t = next token if t == marker: return empty node = new node with key t node.left = build() node.right = build() return node ``` Each recursive call consumes exactly the block of tokens belonging to its own subtree, because a subtree's encoding is self-delimiting: it ends precisely when both of its children's calls have returned. Time is O(n), auxiliary space is O(h) for the recursion stack, where h is the height — O(n) for a degenerate chain, O(log n) for a balanced tree. Recursion depth is real space, so a deep tree may need an explicit stack instead. ### The alternatives, and what each costs - **Level-order with markers.** Same idea driven by a queue instead of recursion; also unambiguous, and often nicer to read for a shallow wide tree. Trailing markers can be trimmed. - **Two traversals instead of markers.** Preorder plus inorder reconstructs a binary tree *if every key is distinct*; so does inorder plus postorder. Preorder plus postorder does **not** — a node with exactly one child looks identical either way, so that pair is unique only for trees where every node has zero or two children. Duplicate keys break all of these pairings, which is one reason the marker form is the safer default. - **Inorder alone.** Useless for reconstruction: for a search tree it is just the sorted key list, which is consistent with every possible shape over those keys. ### Practical traps The marker must be a token that no real key can equal, otherwise a key that happens to look like the marker silently truncates a subtree. Either escape values, or use a delimited/typed encoding where a marker is a distinct token type rather than a magic string. Delimiters matter too: without them, keys `1` and `2` concatenate into something that also reads as `12`. Finally, decode defensively — a truncated stream leaves the recursion asking for tokens that do not exist, and a stream with extra trailing tokens means the sender and receiver disagree about the encoding, both of which should be errors rather than a half-built tree.