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:

"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

Function shape:

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

Examples

Example 1:

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

This is a valid serialization.

The root is 9.

Its left subtree is:

3,4,#,#,1,#,#

Its right subtree is:

2,#,6,#,#

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

Example 2:

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:

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

The part:

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.

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:

-1 + 2 = +1

For a null node, the net change is:

-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:

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:

preorder = "9,#,#"

Start:

slots = 1

Read 9.

It consumes one slot:

slots = 0

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

slots = 2

Read first #.

It consumes one slot:

slots = 1

Read second #.

It consumes one slot:

slots = 0

End of input.

All slots are filled, so the answer is true.

Now take:

preorder = "1,#"

Start:

slots = 1

Read 1.

Consume one slot and create two:

slots = 2

Read #.

Consume one slot:

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

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

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:

slots = 1

This slot is for the root.

For every token:

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

we consume one slot:

slots -= 1

If no slot was available, the serialization is invalid:

if slots < 0:
    return False

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

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

At the end:

return slots == 0

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

Testing

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: