Verify Preorder Serialization of a Binary Tree

medium tree stack string

Problem

Given a comma-separated preorder serialization of a binary tree using # for null, return true if it's a valid serialization.

Inputpreorder = "9,3,4,#,#,1,#,#,2,#,6,#,#"

Outputtrue

Slot counter starts at 1; tracking it through the stream lands exactly at 0.

preorder

def is_valid_serialization(pre):
    slots = 1
    for tok in pre.split(","):
        if slots == 0: return False
        slots += -1 if tok == "#" else 1
    return slots == 0

function isValidSerialization(pre) {
  let slots = 1;
  for (const tok of pre.split(",")) {
    if (slots === 0) return false;
    slots += tok === "#" ? -1 : 1;
  }
  return slots === 0;
}

class Solution {
    public boolean isValidSerialization(String pre) {
        int slots = 1;
        for (String tok : pre.split(",")) {
            if (slots == 0) return false;
            slots += tok.equals("#") ? -1 : 1;
        }
        return slots == 0;
    }
}

bool isValidSerialization(string pre) {
    int slots = 1;
    string tok;
    pre += ",";
    for (char ch : pre) {
        if (ch == ',') {
            if (slots == 0) return false;
            slots += tok == "#" ? -1 : 1;
            tok.clear();
        } else tok += ch;
    }
    return slots == 0;
}

Explanation

Think of building the tree as filling open slots. We start with one empty slot waiting for the root. Each value we place consumes one slot but opens two new ones (its left and right children); each # (null) consumes one slot and opens none.

So we just track a running counter slots starting at 1. For every token, if slots is already 0 we have run out of room but still have tokens left, which is invalid. Otherwise a real value does slots += 1 (uses one, adds two) and a # does slots += -1.

Why it works: a valid binary tree serialization exactly fills every slot it opens. If the counter ever hits zero before the stream ends, there is no place for the next token. If at the very end slots is not 0, some slots were never filled.

Example: "9,3,4,#,#,1,#,#,2,#,6,#,#". Starting at 1: 9 → 2, 3 → 3, 4 → 4, # → 3, # → 2, 1 → 3, # → 2, # → 1, 2 → 2, # → 1, 6 → 2, # → 1, # → 0. It lands exactly on 0, so the answer is true.

This is one pass with just a single integer, so it is fast and uses constant memory.

Time: O(n) Space: O(1)