Verify Preorder Serialization of a Binary Tree: Slot Counting

Given a string of comma-separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Each node value is a non-negative integer, and null nodes are represented by #.

For example, "9,3,4,#,#,1,#,#,2,#,6,#,#" is valid. "1,#" is not.

This is LeetCode 331: Verify Preorder Serialization of a Binary Tree. The problem looks like it should need a stack or a full tree reconstruction, but there is a slicker approach that runs in O(1) space: count available slots.

The key insight: slot counting

Think of the tree as a capacity system. At any point during the preorder scan, you have a number of open "slots" -- positions that still need to be filled by a future token.

You start with 1 slot because the root has to go somewhere.

When you encounter a number (an internal node), it:

• consumes 1 slot (it fills one position)
• opens 2 new slots (for its left and right children)

Net effect: +1 slot.

When you encounter a # (a null), it:

• consumes 1 slot
• opens nothing (nulls have no children)

Net effect: -1 slot.

Two conditions must hold for a valid serialization:

1. Slots never go negative during the scan. Going negative mid-way means you have more leaves than the tree can support at that point.
2. Slots equal exactly 0 at the end. Zero means every opened slot has been filled.

Why does this work? Every valid binary tree with n internal nodes has exactly n+1 leaves (a well-known property of full binary trees). The slot count tracks that invariant in real time: each internal node produces a net +1, each null consumes a net -1, and the total sums to zero.

The solution

def isValidSerialization(preorder: str) -> bool:
    slots = 1
    for token in preorder.split(','):
        slots -= 1
        if slots < 0:
            return False
        if token != '#':
            slots += 2
    return slots == 0

The loop structure is deliberate. You decrement first and check immediately. That catches the case where slots would go negative before you process the token's children. Then you add 2 only for non-null tokens.

The final return slots == 0 catches the case where the string ran out of tokens before all slots were filled (slots > 0) or over-filled the tree (slots would have gone negative, already caught).

Step-by-step walkthrough

Let's trace through "9,3,4,#,#,1,#,#,2,#,6,#,#" with the slot counter.

Watch how slots bounce up and down as you process numbers and nulls. The key guarantee is that the count never dips below 1 mid-stream (after consuming a token but before the scan is done) and lands on exactly 0 at the last token.

Complexity analysis

Time is O(n) for slot counting. You iterate through all n tokens exactly once. Splitting the string is also O(n).

Space is O(1) for slot counting. You only track a single integer. This is the main advantage over the stack approach.

Alternative: stack-based reduction

If you prefer a more visual approach, a stack works too. Push each token onto the stack. After every push, check if the top three elements are [number, #, #]. If they are, pop all three and push a single # in their place -- you just collapsed a leaf node into a null marker.

At the end, the stack should contain exactly one element: #.

def isValidSerialization(preorder: str) -> bool:
    stack = []
    for token in preorder.split(','):
        stack.append(token)
        while len(stack) >= 3 and stack[-1] == '#' and stack[-2] == '#' and stack[-3] != '#':
            stack.pop()
            stack.pop()
            stack.pop()
            stack.append('#')
    return stack == ['#']

This mirrors what a real parser would do: recognize a complete subtree (root + two null children) and replace it with a single null. The slot-counting approach is mathematically equivalent but skips the explicit stack.

Building blocks

Greedy slot counting. The idea that each token either opens or closes capacity is a reusable framing. You see the same pattern in Valid Parentheses where open brackets add capacity and close brackets consume it. The difference here is that numbers add 2 and consume 1 (net +1) while nulls consume 1 (net -1). Once you see the mapping, the algorithm writes itself.

Tree degree invariant. Every full binary tree (where every node has 0 or 2 children) has exactly one more leaf than internal node. The slot counter is just tracking this invariant live during the scan. If you have seen k internal nodes and m nulls so far, the current slot count equals 1 + k - m. Valid serializations satisfy 1 + total_internal - total_nulls = 0, which means total_nulls = total_internal + 1.

Edge cases

• Single "#". This represents an empty tree. You start with 1 slot, consume it (slots = 0), do not add 2 (it is a null), and return slots == 0, which is True. An empty tree is valid.
• Single number like "1". You start with 1 slot, consume it (slots = 0), add 2 (slots = 2), and return slots == 0, which is False. A single number with no children and no null markers is not a complete serialization.
• "#,1" or any string starting with # followed by more tokens. After consuming #, slots = 0. Decrementing again for the next token gives slots = -1, which triggers an early False. Once you hit a null at the root position, there is no room for any further tokens.
• Repeated numbers with no nulls. Something like "1,2,3". After processing 1 you have 2 slots, after 2 you have 3 slots, after 3 you have 4 slots. You reach the end with slots = 4, not 0, so the function returns False.
• Correct count but wrong structure. Slot counting catches structural issues in real time because of the "never go negative" check. A string that momentarily exhausts all open slots then tries to add more tokens will be caught immediately.

From understanding to recall

You just saw how a single integer can verify an entire tree serialization. The slot counter starts at 1, ticks up by 1 for each number, ticks down by 1 for each null, and must end at 0 without ever going negative. That is the whole algorithm.

But will you reconstruct it cleanly under pressure? The tricky part is remembering to decrement before checking, not after. If you check after, you miss the case where a token would bring slots to -1 at the very end. And you need to remember that the number contributes a net +1, not +2, because it also consumes the slot it fills.

Spaced repetition builds that recall. You write the five-line function from scratch after one day, then three days, then a week. Each time, you reconstruct the decrement-then-check-then-maybe-add order from memory. After a few sessions, it becomes automatic.

Slot counting is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling the building blocks individually, rather than grinding random problems, is how you build durable pattern recognition.

Related posts

• Serialize and Deserialize Binary Tree - the full serialize/deserialize implementation
• Binary Tree Preorder Traversal - what preorder traversal looks like
• Validate Binary Search Tree - another tree validation problem