A preorder list tells us which node is visited first, but a value list alone need not reveal which children are absent. For instance, a root with only a left child and a root with only a right child can have the same preorder values. Add a special null marker at every empty child and the stream records both values and shape.
This derived application extends the course's binary-tree traversal and reconstruction unit.
1. Encoding and a precise format
A binary tree is finite and ordered: left and right child positions are distinct. Values may repeat. Use a special token # for an empty subtree, and assume it cannot be confused with any encoded value token. Serialize recursively:
encode(node):
if node is null: emit #; return
emit VALUE(node.value)
encode(node.left)
encode(node.right)
VALUE(v) is a tagged value token, not a bare string that could be mistaken for #. This distinction matters in a real format even if an example abbreviates it as a letter. An empty tree encodes as the single token #.
Definition 4.3.1
(Null-marked preorder encoding)
For a finite ordered binary tree , its null-marked preorder encoding is the token sequence defined by and, for a node with value , left subtree and right subtree , . The first token is the root's value or the marker.
Worked example 4.3.2
(Encoding a tree with a missing left child)
For example, let have left child and right child , and let have only right child ; are leaves. The encoding is
A B # D # # C # #
The first # marks the missing left child of ; the next two close , and the last two close . Merely appending nulls to the end would not preserve the positions of those missing children.
Counterexample mode
Values alone do not determine the tree
A tempting claim is that the preorder list of values already determines the tree. Take , with root and only a left child , and , with root and only a right child . Both have the preorder values , yet they are different ordered trees. With markers, encodes as A B # # # and as A # B # #: the position of the first marker records which child is missing. The repair is a marker at every empty child.
2. Decode one subtree at a time
decodeOne(tokens, position):
if position == length(tokens): fail "truncated"
token = tokens[position]; position += 1
if token == #: return (null, position)
if token is not a valid VALUE: fail "invalid token"
(left, position) = decodeOne(tokens, position)
(right, position) = decodeOne(tokens, position)
return (new node(token.value, left, right), position)
decodeTree(tokens):
(root, position) = decodeOne(tokens, 0)
if position != length(tokens): fail "extra tokens"
return root
decodeOne consumes exactly one complete subtree, returning where the next subtree begins. A non-null token first fixes the root value; the next complete subtree is its left child, and the following complete subtree is its right child. A null token consumes one position and has no children. The outer check rejects an otherwise complete tree followed by extra tokens. A production implementation should release any nodes it allocated if parsing later fails; the pseudocode specifies the result, not a language-specific ownership policy.
Theorem 4.3.3
(Decoding inverts encoding)
For every finite ordered binary tree , decodeTree(encode(T)) returns a tree with the same shape and the same values as . Conversely, every token stream accepted by decodeTree is the encoding of exactly one such tree, even when values repeat.
Proof
(Induction on the tree)
By induction on the encoded tree, the decoder consumes exactly its encoding and reconstructs its root and both children. Conversely, the first token of any successfully decoded subtree determines whether it is empty or gives its root value, and recursive parsing uniquely determines each child and the token boundary. Thus a valid complete stream represents exactly one ordered tree, including when values repeat.
3. Validate shape by counting open slots
Definition 4.3.4
(Open slots and the slot count)
A slot is a position awaiting an entire subtree. Start with one root slot. Each token fills one slot. A null marker creates none, so the count decreases by 1. A value token creates two child slots, so the net change is . Reject an invalid token. Reject if the slot count is already zero before the next token; accept only if it becomes zero exactly at the end. For an empty stream the count remains 1 and the stream is truncated.
Theorem 4.3.5
(Slot counting accepts exactly the complete streams)
Let a stream have tokens, each either # or a valid value token. Put , and let if token is a value and if it is #. Then decodeTree accepts the stream exactly when for every and .
Proof
(Slots as pending recursive calls)
This is sufficient as well as necessary. At every prefix, slots correspond to the pending recursive child calls in preorder. A value replaces the next pending call by two calls, left before right; # completes it. A positive count guarantees a place for the next token, and final zero means no pending calls remain. Thus the complete stream follows the recursive grammar. The count checks shape, while each value token must independently satisfy its format.
Proof X-ray
What does the slot count remember?
The count records how many subtree positions remain unfinished; it does not store the node values or identify the shape on its own. The recursive parser also uses the token order, taking the entire left subtree before the right. A final count of zero certifies a complete stream only when no earlier prefix has already exhausted all slots.
For a tree with real nodes, there are null markers. Each node has two child slots, so there are child slots; a nonempty tree has real child edges and hence empty child slots. For , the one root slot itself gives the single marker. The complete stream has tokens. This count alone is not enough: # A # has one value and two markers but finishes its root before the extra tokens.
Worked example 4.3.6
(Slot counts along an encoding)
Take the stream A B # D # # C # # from the encoding section. The count starts at 1 and changes as follows.
| Token | Change | Slots after |
|---|---|---|
| start | 1 | |
A | +1 | 2 |
B | +1 | 3 |
# | −1 | 2 |
D | +1 | 3 |
# | −1 | 2 |
# | −1 | 1 |
C | +1 | 2 |
# | −1 | 1 |
# | −1 | 0 |
The count is at least 1 before every token and equals 0 exactly at the end, so the stream is accepted, in agreement with the decoder.
Worked example 4.3.7
(Edge cases: the empty tree, one node and bad streams)
The stream # has count : it is accepted and decodes to the empty tree. The stream A # # has counts : a single node with no children. The stream A # ends with count 1, so the decoder runs out of tokens while reading the right child and fails with "truncated". The stream # A # has count 0 after its first token, while two tokens remain: decodeOne returns the empty tree after one token, decodeTree finds position 1 different from length 3, and fails with "extra tokens".
Common mistake
(Counting tokens instead of slots)
The counts tokens and markers are necessary but not sufficient. The stream # A # has three tokens, one value and two markers, matching , yet it is not an encoding: the first marker completes the whole tree and the remaining tokens are extra. The slot count catches it, since the count is 0 after the first token while tokens remain.
Common mistake
(Skipping the check for leftover tokens)
If decodeTree returned the result of decodeOne without comparing position with the length, then # A # would silently decode as the empty tree and two tokens would be ignored. A complete-subtree parse is not yet a complete-stream parse.
4. Cost and limits
Theorem 4.3.8
(Cost of encoding, decoding and validation)
Let a tree have nodes and height (the maximum number of real nodes on a root-to-leaf path, for the empty tree). Under constant-time token operations, encoding and decoding each take time, with the stream of tokens as output or input. The recursive stack uses space, which is for a chain. Slot-only validation takes time and counters of sufficient range, excluding the input storage, and does not construct the tree.
Proof
(One token per step)
The encoder emits one token per call and makes exactly calls, one for each node and one for each empty child. The decoder consumes at least one token per call and makes one call per token. The recursion depth is at most one more than the height. The validator reads each token once and keeps one counter.
These bounds assume values fit the stated constant-time token model; copying variable-length values adds their total size. Null-marked preorder is a different representation from ordinary preorder. The special marker and full-stream validation are part of the contract.
5. Exercises with solutions
Quick check
(Encode the tree whose root has only a left child , and is a leaf.)
Write , then the left subtree, then the right subtree.
Solution · Answer
X Y # # #. The root is followed by the encoding of its left subtree, Y # #, and then by the marker # for the empty right subtree.
Quick check
(Does A # B # # decode, and to what tree? Check with the slot count.)
Track the count token by token.
Solution · Answer
The counts are , positive before every token and zero at the end. The stream decodes to a root with an empty left subtree and a right child that is a leaf.
Quick check
(How many tokens, and how many markers, does the encoding of a tree with 7 nodes have?)
Use the counts and .
Solution · Answer
It has tokens, of which are markers and 7 are values.