LeetCode 331 - Verify Preorder Serialization of a Binary Tree

LeetCode Problem 331

Difficulty: 🟡 Medium
Topics: String, Stack, Tree, Binary Tree

Solution

Problem Understanding

The problem gives us a string that represents the preorder serialization of a binary tree. Each value is separated by commas. A normal integer represents a real tree node, while the character '#' represents a null pointer.

In preorder traversal, we always visit nodes in this order:

1. Current node
2. Left subtree
3. Right subtree

For example, the serialization:

9,3,4,#,#,1,#,#,2,#,6,#,#

means:

• 9 is the root
• 3 is the left child of 9
• 4 is the left child of 3
• #,# means 4 has no children
• 1 becomes the right child of 3
• and so on

The task is to determine whether the given serialization could represent a valid binary tree, without actually reconstructing the tree.

The constraints are important:

• The input length can be up to 10^4
• Values are already guaranteed to be syntactically valid
• We are explicitly told not to rebuild the tree

These constraints strongly suggest that we should process the string directly in a single pass.

Several edge cases are especially important:

• A single "#" is a valid tree, representing an empty tree.
• "1,#" is invalid because the root node still needs one more child.
• "9,#,#,1" is invalid because the tree is already complete before the extra node appears.
• Extra nodes after a completed tree must immediately invalidate the serialization.
• Null-only structures must still obey preorder structure rules.

A naive implementation that tries to partially reconstruct trees can become unnecessarily complicated and waste memory.

Approaches

Brute Force Approach

A straightforward approach is to reconstruct the binary tree while reading the preorder traversal.

We could recursively process tokens:

• If the current token is '#', return None
• Otherwise create a node
• Recursively build the left subtree
• Recursively build the right subtree

After construction, the serialization is valid only if all tokens were consumed exactly once.

This works because preorder traversal uniquely determines the tree structure when null markers are included.

However, this approach violates the spirit of the problem because we are explicitly told not to reconstruct the tree. It also uses unnecessary memory for node allocation and recursion.

Optimal Approach, Slot Counting

The key observation is that every node in a binary tree occupies one incoming connection slot.

Initially, the root needs one slot.

Then:

• A non-null node consumes one slot and creates two new slots
• A null node consumes one slot and creates zero new slots

This leads to a very elegant validation rule.

We start with one available slot.

For every token:

1. Consume one slot
2. If slots become negative, the serialization is invalid
3. If the token is not '#', add two new slots

At the end:

• The serialization is valid only if all slots are exactly used up
• Therefore, the final slot count must be zero

This solution avoids tree construction entirely and processes the input in one pass.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Reconstructs the tree recursively
Optimal	O(n)	O(1)	Uses slot counting without building the tree

Algorithm Walkthrough

Optimal Algorithm Using Slot Counting

1. Split the input string by commas to obtain all preorder tokens.

Each token represents either a real node or a null node. 2. Initialize a variable called slots to 1.

A binary tree root always requires one available parent slot. 3. Iterate through each token in order.

Before processing a token, consume one slot because every node, including null nodes, must occupy a position in the tree. 4. If slots becomes negative at any point, return False.

This means we encountered more nodes than the tree structure can support. 5. If the current token is not '#', add two new slots.

A real node creates space for a left child and a right child. 6. Continue processing until all tokens are consumed. 7. After processing all tokens, check whether slots == 0.

If zero slots remain, the serialization used exactly the correct number of child positions. 8. Return the result of that check.

Why it works

The algorithm maintains an invariant:

• slots always represents the number of child positions still available in the partially processed tree.

Every node must occupy exactly one slot. Real nodes then generate two additional child positions.

A valid preorder serialization must consume all available positions exactly. If slots become negative, the traversal attempted to place nodes where no parent position existed. If slots remain positive at the end, some expected children were never provided.

Because preorder traversal processes nodes in the same order the tree structure expands, slot accounting perfectly captures structural validity.

Python Solution

class Solution:
    def isValidSerialization(self, 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 implementation directly follows the slot counting algorithm.

We begin with one available slot for the root node. Then we iterate through every token in the preorder serialization.

Each token consumes one slot because every node must occupy a position in the tree. If the slot count becomes negative, we immediately know the structure is invalid because there was no available parent position.

Whenever the token represents a real node rather than '#', we add two new slots for its children.

At the end, we verify that all slots were consumed exactly. A valid tree serialization cannot leave unused child positions.

This implementation is concise because the slot-counting observation completely eliminates the need for stacks, recursion, or tree construction.

Go Solution

package main

import "strings"

func isValidSerialization(preorder string) bool {
    slots := 1
    tokens := strings.Split(preorder, ",")

    for _, token := range tokens {
        slots--

        if slots < 0 {
            return false
        }

        if token != "#" {
            slots += 2
        }
    }

    return slots == 0
}

The Go implementation mirrors the Python solution closely.

The primary difference is that Go uses strings.Split to tokenize the input string. The slot logic remains identical.

Since the problem constraints are small and node values are limited, there are no integer overflow concerns. We also do not need additional data structures because the slot-counting method uses constant extra memory.

Worked Examples

Example 1

Input: "9,3,4,#,#,1,#,#,2,#,6,#,#"

Initial state:

slots = 1

Token	Slots Before	Consume Slot	Add Slots	Slots After
9	1	0	+2	2
3	2	1	+2	3
4	3	2	+2	4
#	4	3	+0	3
#	3	2	+0	2
1	2	1	+2	3
#	3	2	+0	2
#	2	1	+0	1
2	1	0	+2	2
#	2	1	+0	1
6	1	0	+2	2
#	2	1	+0	1
#	1	0	+0	0

Final slots equal zero, so the serialization is valid.

Result:

true

Example 2

Input: "1,#"

Initial state:

slots = 1

Token	Slots Before	Consume Slot	Add Slots	Slots After
1	1	0	+2	2
#	2	1	+0	1

After processing all tokens, one slot remains unused.

This means the root node is still missing one child.

Result:

false

Example 3

Input: "9,#,#,1"

Token	Slots Before	Consume Slot	Add Slots	Slots After
9	1	0	+2	2
#	2	1	+0	1
#	1	0	+0	0
1	0	-1	+2	Invalid

The tree becomes complete after the third token. The extra node 1 has nowhere to attach.

Result:

false

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each token is processed exactly once
Space	O(1)	Only a few integer variables are used

The algorithm scans the serialization exactly once, making the runtime linear in the number of tokens.

The extra space usage is constant because we only maintain the slot counter. No recursion, stack, or tree structure is created.

Test Cases

solution = Solution()

assert solution.isValidSerialization("9,3,4,#,#,1,#,#,2,#,6,#,#") == True
# Valid complex tree

assert solution.isValidSerialization("1,#") == False
# Root missing one child

assert solution.isValidSerialization("9,#,#,1") == False
# Extra node after tree completion

assert solution.isValidSerialization("#") == True
# Empty tree

assert solution.isValidSerialization("1,#,#") == True
# Single valid node

assert solution.isValidSerialization("#,#") == False
# Extra null after empty tree

assert solution.isValidSerialization("1,2,#,#,#") == True
# Valid left-heavy structure

assert solution.isValidSerialization("1,2,#") == False
# Incomplete serialization

assert solution.isValidSerialization("1,#,#,#") == False
# Extra null node

assert solution.isValidSerialization("7,2,#,2,#,#,#") == True
# Valid asymmetric tree

assert solution.isValidSerialization("7,2,#,2,#,#") == False
# Missing final null

assert solution.isValidSerialization("9,#,92,#,#") == True
# Multi-digit values

Test Summary

Test	Why
"9,3,4,#,#,1,#,#,2,#,6,#,#"	Standard valid example
"1,#"	Detects incomplete tree
"9,#,#,1"	Detects extra nodes after completion
"#"	Valid empty tree
"1,#,#"	Smallest valid non-empty tree
"#,#"	Invalid extra null node
"1,2,#,#,#"	Valid left subtree structure
"1,2,#"	Missing children
"1,#,#,#"	Tree completed too early
"7,2,#,2,#,#,#"	Valid asymmetric tree
"7,2,#,2,#,#"	Missing final child marker
"9,#,92,#,#"	Handles multi-digit values

Edge Cases

One important edge case is the empty tree serialization:

"#"

This is valid because a null root represents an empty binary tree. A naive implementation might incorrectly reject it because there are no actual node values. The slot-counting approach handles this naturally. We start with one slot, the '#' consumes it, and we finish with exactly zero slots.

Another critical edge case occurs when the tree becomes complete before all tokens are processed:

"9,#,#,1"

After processing "9,#,#", the slot count becomes zero, meaning the entire tree is already finished. The extra "1" attempts to consume a nonexistent slot, causing the count to become negative. The algorithm immediately rejects the serialization.

A third tricky edge case is an incomplete tree:

"1,#"

The root node still requires one more child, but the input ends too early. The final slot count remains positive, indicating unresolved child positions. The implementation correctly returns False because a valid binary tree must consume every slot exactly.

Another subtle case involves consecutive null markers:

"#,#"

The first '#' already completes the entire tree. The second '#' attempts to consume an additional slot, making the slot count negative. This prevents invalid serializations from slipping through.