331. Verify Preorder Serialization of a Binary Tree

Time: O(n)

Space: O(1)

Intuition

Use slot counting: the root consumes 1 slot and produces 2 child slots. A null ("#") consumes 1 slot and produces 0. Start with 1 slot (for the root). The sequence is valid iff slots never go negative and ends at exactly 0.

Algorithm

1slots = 1.
2For each token in preorder.Split(","):
3 slots-- (consume one slot). If slots < 0, return false.
4 If token != "#": slots += 2 (add two child slots).
5Return slots == 0.

Example Walkthrough

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

1.slots=1. "9":-1+2=2. "3":1+2=3. "4":2+2=4. "#":3. "#":2. "1":1+2=3. "#":2. "#":1. "2":0+2=2. "#":1. "6":0+2=2. "#":1. "#":0.
2.slots=0 -> true.

Output: true

Common Pitfalls

•The slot count must stay non-negative throughout - not just be 0 at the end.

331.cs

// Approach: Track available slots (starts at 1); each internal node consumes
// one slot but adds two; null nodes consume one. Valid if slots reach exactly 0.
// Time: O(n) Space: O(1)

public class Solution
{
    public bool IsValidSerialization(string preorder)
    {
        int degree = 1; // out-degree (children) - in-degree (parent)

        foreach (var node in preorder.Split(','))
        {
            if (--degree < 0) // One parent
                return false;
            if (node != "#")
                degree += 2; // Two children
        }

        return degree == 0;
    }
}

Was this solution helpful?