331 · Verify Preorder Serialization of a Binary Tree

A traversal problem with no tree in it. You are handed the comma-separated preorder of a binary tree, with # standing in for every null child, and asked whether it could have come from a real tree — without reconstructing one. The whole solution is a single integer counting unfilled slots.

1 — The idea

Think of the tree as a set of slots waiting to be filled. Before you read anything there is exactly one: the root's. Then, reading left to right:

• Every token — value or # — fills one slot. So every token costs 1.
• A real value is an internal node, so it opens two new slots for its own left and right children. Net effect: +1.
• A # opens none. Net effect: −1.

The string is valid exactly when the count never goes negative and lands on zero. Negative means a token arrived with no slot to hold it — the tree was already complete. Positive at the end means slots were left unfilled — the string stopped early. Both are malformed, and they are the only two ways to be malformed.

Preorder is what makes this work: a node is written before its children, so its slots are always opened before anything tries to fill them. The same counting argument does not hold for inorder.

2 — A valid string

"9,3,4,#,#,1,#,#,2,#,6,#,#" — the serialization of a real tree. Step through and watch the count rise as internal nodes appear and drain as the nulls close them off.

int slots = 1;                        // the root's slotfor (String tok : preorder.split(",")) {    slots--;                          // this token fills one    if (slots < 0) return false;        // no slot to fill    if (!tok.equals("#")) slots += 2;   // a real node opens two}return slots == 0;

The count reaches 0 for the first time on the very last token. That is the signature of a well-formed string: it can touch zero only at the end, never before.

3 — Too many nodes

"9,#,#,1". After 9,#,# the tree is a complete single node with both children null — there is nothing left to attach to.

int slots = 1;                        // the root's slotfor (String tok : preorder.split(",")) {    slots--;                          // this token fills one    if (slots < 0) return false;        // no slot to fill    if (!tok.equals("#")) slots += 2;   // a real node opens two}return slots == 0;

The scan returns false at the fourth token and never reads further. This early exit is not just an optimisation: without the slots < 0 check, a trailing 1 would bump the count back up to 1, a following #,# would drive it to 0, and the function would wrongly report true. Checking only the final value is the classic wrong answer here.

4 — Not enough nodes

"1,#". Node 1 opens two slots; only one gets filled.

int slots = 1;                        // the root's slotfor (String tok : preorder.split(",")) {    slots--;                          // this token fills one    if (slots < 0) return false;        // no slot to fill    if (!tok.equals("#")) slots += 2;   // a real node opens two}return slots == 0;

The string runs out with a slot still open, so the answer is false. This is the failure the final slots == 0 test catches, and it is why returning true as soon as the count first hits zero would also be wrong — you need both conditions.

5 — Complexity and edge cases

• Time: O(n) in the length of the string, one pass.
• Space: O(1) if you scan the string manually, or O(n) if you call split first, which materialises the token array. The counter itself is a single int.
• "#" alone is valid: it is the serialization of the empty tree. Slots go 1 → 0, and the loop ends at zero.
• An empty string is not valid input per the constraints, but if you have to handle it, note that "".split(",") in Java returns [""], not an empty array — a real trap.
• Multi-digit values matter only if you scan character by character; splitting on commas handles them for free.
• Do not build the tree. Reconstructing it and checking validity afterwards is O(n) too, but it is far more code and far more places to be wrong under time pressure.

6 — Reference implementation

public boolean isValidSerialization(String preorder) {
    int slots = 1;                          // the root's slot
    for (String tok : preorder.split(",")) {
        slots--;                            // every token fills exactly one
        if (slots < 0) return false;          // nothing left to attach to
        if (!tok.equals("#")) slots += 2;     // internal node opens two
    }
    return slots == 0;                     // and none left over
}

An equivalent framing some people find easier to recall: count nodes and nulls, and require nulls == nodes + 1 at the end, with nulls never exceeding nodes + 1 along the way. It is the same invariant with the sign flipped. This problem is marked optional because it is elegant but teaches nothing structural — there is no traversal here to transfer to another question.