# LeetCode 331: Verify Preorder Serialization of a Binary Tree

## Problem Restatement

We are given a string `preorder`.

The string represents a preorder traversal serialization of a binary tree.

Each token is separated by a comma.

A non-null node is written as an integer.

A null child is written as `#`.

For example:

```text
"9,3,4,#,#,1,#,#,2,#,6,#,#"
```

We need to return `true` if this string is a valid preorder serialization of some binary tree.

We are not allowed to reconstruct the tree. The input format itself is valid, so we do not need to handle cases like `"1,,3"`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A comma-separated preorder string |
| Output | `true` if it is a valid serialization, otherwise `false` |
| Null marker | `#` |
| Non-null node | An integer |
| Restriction | Do not rebuild the tree |

Function shape:

```python
def isValidSerialization(preorder: str) -> bool:
    ...
```

## Examples

Example 1:

```text
Input: preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#"
Output: true
```

This is a valid serialization.

The root is `9`.

Its left subtree is:

```text
3,4,#,#,1,#,#
```

Its right subtree is:

```text
2,#,6,#,#
```

Every non-null node has exactly two child slots, and every slot is filled.

Example 2:

```text
Input: preorder = "1,#"
Output: false
```

The node `1` has a left child `#`, but its right child is missing.

So the serialization is incomplete.

Example 3:

```text
Input: preorder = "9,#,#,1"
Output: false
```

The part:

```text
9,#,#
```

already forms a complete tree.

The extra `1` has no available parent slot.

So the serialization is invalid.

## First Thought: Rebuild the Tree

One possible idea is to parse the preorder string and recursively build the tree.

For each non-null node, build its left child and right child.

For each `#`, return a null node.

But the problem explicitly says we should not reconstruct the tree.

We only need to verify structure.

So we should track how many child positions are available.

## Key Insight

Think of the serialization as filling empty slots.

At the start, there is one slot available for the root.

```text
slots = 1
```

Each token consumes one slot.

If the token is `#`, it consumes a slot and creates no new slots.

If the token is a number, it consumes one slot but creates two child slots.

So for a non-null node, the net change is:

```text
-1 + 2 = +1
```

For a null node, the net change is:

```text
-1
```

At any point, if we need to consume a slot but there are no slots left, the serialization is invalid.

At the end, every slot must be filled, so `slots` must be exactly `0`.

## Algorithm

Split `preorder` by commas.

Set:

```python
slots = 1
```

Then scan each token from left to right.

For each token:

1. Consume one slot.
2. If `slots` becomes negative, return `False`.
3. If the token is not `#`, add two slots.
4. Continue.

At the end, return whether `slots == 0`.

## Walkthrough

Take:

```text
preorder = "9,#,#"
```

Start:

```text
slots = 1
```

Read `9`.

It consumes one slot:

```text
slots = 0
```

It is a non-null node, so it creates two child slots:

```text
slots = 2
```

Read first `#`.

It consumes one slot:

```text
slots = 1
```

Read second `#`.

It consumes one slot:

```text
slots = 0
```

End of input.

All slots are filled, so the answer is `true`.

Now take:

```text
preorder = "1,#"
```

Start:

```text
slots = 1
```

Read `1`.

Consume one slot and create two:

```text
slots = 2
```

Read `#`.

Consume one slot:

```text
slots = 1
```

End of input.

One slot remains unfilled, so the answer is `false`.

## Correctness

A valid binary tree serialization must fill exactly one root slot at the beginning.

Every token in preorder fills exactly one currently available slot.

A null marker `#` fills one slot and creates no children.

A non-null node fills one slot and creates two new child slots.

The algorithm models this process exactly.

If `slots` becomes negative, then the serialization tries to place a node after all available child positions have already been filled. No binary tree can have such a serialization.

If the scan ends with `slots > 0`, then some child positions were never filled. The serialization is incomplete.

If the scan ends with `slots == 0`, then every created child position was filled exactly once, and no token appeared after the tree was complete. Therefore the serialization represents a valid binary tree.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We scan each token once |
| Space | `O(n)` | `split(",")` creates a token list |

Here, `n` is the length of the input string.

We can reduce extra space by scanning the string manually, but `split` is simpler and accepted.

## Implementation

```python
class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        slots = 1

        for node in preorder.split(","):
            slots -= 1

            if slots < 0:
                return False

            if node != "#":
                slots += 2

        return slots == 0
```

## Code Explanation

We begin with one available slot:

```python
slots = 1
```

This slot is for the root.

For every token:

```python
for node in preorder.split(","):
```

we consume one slot:

```python
slots -= 1
```

If no slot was available, the serialization is invalid:

```python
if slots < 0:
    return False
```

If the token is a real node, it creates two child slots:

```python
if node != "#":
    slots += 2
```

At the end:

```python
return slots == 0
```

The serialization is valid only when all slots have been filled.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.isValidSerialization("9,3,4,#,#,1,#,#,2,#,6,#,#") == True
    assert s.isValidSerialization("1,#") == False
    assert s.isValidSerialization("9,#,#,1") == False

    assert s.isValidSerialization("#") == True
    assert s.isValidSerialization("#,#") == False
    assert s.isValidSerialization("1,#,#") == True
    assert s.isValidSerialization("1,2,#,#,#") == True
    assert s.isValidSerialization("1,2,#,#") == False

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Full sample | Valid larger tree |
| `"1,#"` | Missing right child |
| `"9,#,#,1"` | Extra node after complete tree |
| `"#"` | Empty tree |
| `"#,#"` | Extra null after complete tree |
| `"1,#,#"` | Single root with two null children |
| `"1,2,#,#,#"` | Valid tree with left child |
| `"1,2,#,#"` | Missing root right child |