LeetCode 331: Verify Preorder Serialization of a Binary Tree Solution in Python – A Step-by-Step Guide

What Is LeetCode 331: Verify Preorder Serialization of a Binary Tree?

In LeetCode 331: Verify Preorder Serialization of a Binary Tree, you’re given a string preorder representing a preorder traversal of a binary tree, where numbers are nodes and "#" denotes null. Your task is to determine if it’s a valid serialization—meaning it fully constructs a binary tree without leftover or missing nodes. For example, "9,3,4,#,#,1,#,#,2,#,6,#,#" is valid, but "1,#" isn’t. This problem tests your ability to validate tree structure, connecting to concepts in LeetCode 144: Binary Tree Preorder Traversal.

Problem Statement

• Input: A string preorder (comma-separated values, numbers or "#").
• Output: A boolean—True if valid preorder serialization, False otherwise.
• Rules:
• Preorder: root, left subtree, right subtree.
• "#" represents a null node.
• Must form a complete binary tree.

Constraints

• 1 <= preorder.length <= 10⁴
• preorder contains only commas, digits, and "#".
• No leading zeros in numbers.

Examples

• Input: "9,3,4,#,#,1,#,#,2,#,6,#,#"
• Output: True (Valid tree: 9(root), left=3(4,#,#), right=2(1,#,#,6,#,#))
• Input: "1,#"
• Output: False (Incomplete: missing right subtree)
• Input: "#"
• Output: True (Single null node)

Understanding the Problem: Verifying the Tree

To solve LeetCode 331: Verify Preorder Serialization of a Binary Tree in Python, we need to check if the preorder string forms a valid binary tree—each non-null node has two children (possibly null), and no nodes are left unprocessed or missing. A naive approach—reconstructing the tree—is O(n) time and space, but we can optimize further. We’ll use:

• Best Solution (Slot Counting): O(n) time, O(1) space—fast and space-efficient.
• Alternative Solution (Stack-Based): O(n) time, O(n) space—clear but uses more memory.

Let’s start with the slot-counting solution, explained in a beginner-friendly way.

Best Solution: Slot Counting

Why This Is the Best Solution

The slot-counting approach is the top choice for LeetCode 331 because it’s efficient—O(n) time, O(1) space—and uses a clever capacity-tracking method. It processes the string as a sequence of slots (available child positions), adjusting the count based on nodes and nulls, without needing a stack. It’s like keeping a tally of open spots as you build—simple and brilliant!

How It Works

Think of this as a slot manager:

• Step 1: Initialize Slots:
• Start with 1 slot (for the root).
• Step 2: Process Nodes:
• Each value (node or #) uses 1 slot.
• Non-null node adds 2 slots (for left and right children).
• Net effect: node -1 + 2 = +1, null -1 = -1.
• Step 3: Validate:
• Slots must never go negative (no deficit).
• End with 0 slots (all used).
• Step 4: Why It Works:
• Preorder ensures left-to-right processing.
• Slot balance reflects tree completeness.

It’s like counting chairs for guests—perfect balance!

Step-by-Step Example

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

• Init: slots = 1
• 9: slots = 1-1+2 = 2 (root adds 2 children)
• 3: slots = 2-1+2 = 3
• 4: slots = 3-1+2 = 4
• #: slots = 4-1 = 3
• #: slots = 3-1 = 2
• 1: slots = 2-1+2 = 3
• #: slots = 3-1 = 2
• #: slots = 2-1 = 1
• 2: slots = 1-1+2 = 2
• #: slots = 2-1 = 1
• 6: slots = 1-1+2 = 2
• #: slots = 2-1 = 1
• #: slots = 1-1 = 0
• Result: slots = 0, True

Example: "1,#"

• Init: slots = 1
• 1: slots = 1-1+2 = 2
• #: slots = 2-1 = 1 (should be 0, incomplete)
• Result: False

Code with Detailed Line-by-Line Explanation

Copy codeclass Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        # Split into nodes
        nodes = preorder.split(',')

        # Initialize slots (capacity for children)
        slots = 1

        # Process each node
        for node in nodes:
            slots -= 1  # Use one slot
            if slots < 0:  # Deficit before adding slots
                return False
            if node != '#':  # Non-null adds 2 slots
                slots += 2

        # All slots must be used
        return slots == 0

• Line 3: Split string into node list.
• Line 6: Start with 1 slot for root.
• Lines 9-13: Process nodes:
• Decrease slot for current node.
• Check for deficit (invalid if negative).
• Add 2 slots for non-null nodes.
• Line 15: Valid if slots = 0.
• Time Complexity: O(n)—single pass (n = string length).
• Space Complexity: O(1)—just slots variable (excluding input split).

This is like a slot-counting maestro—fast and lean!

Alternative Solution: Stack-Based

Why an Alternative Approach?

The stack-based approach—O(n) time, O(n) space—uses a stack to simulate tree construction, collapsing null children as they appear. It’s more intuitive for visualizing the preorder process but uses extra space. It’s like building the tree step-by-step—clear and hands-on!

How It Works

Simulate with a stack:

• Step 1: Push nodes onto stack.
• Step 2: When hitting "#":
• Pop if last two are "#" and a number, replace with "#".
• Step 3: Check if stack ends with single "#".

Step-by-Step Example

Example: "9,3,4,#,#"

• Stack: []
• 9: [9]
• 3: [9,3]
• 4: [9,3,4]
• #: [9,3,4,#]
• #: [9,3,4,#,#] → [9,3,#] (collapse 4,#,#)
• Result: Not done yet, but valid so far (full string would collapse to [#])

Code for Stack-Based Approach

Copy codeclass Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        nodes = preorder.split(',')
        stack = []

        for node in nodes:
            while (len(stack) >= 2 and 
                   stack[-1] == '#' and stack[-2] != '#' and node == '#'):
                stack.pop()  # Pop '#'
                stack.pop()  # Pop number
                stack.append('#')  # Replace with '#'
            stack.append(node)

        return len(stack) == 1 and stack[0] == '#'

• Time Complexity: O(n)—single pass with stack ops.
• Space Complexity: O(n)—stack size.

It’s a stack-driven tree builder—vivid but heavier!

Comparing the Two Solutions

• Slot Counting (Best):
• Pros: O(n) time, O(1) space, no extra data structure.
• Cons: Abstract slot concept.
• Stack-Based (Alternative):
• Pros: O(n) time, O(n) space, mimics tree building.
• Cons: More space, complex collapse logic.

Slot counting wins for efficiency.

Additional Examples and Edge Cases

• "#": True.
• "1,#,#": True.
• "1,2": False.

Both handle these well.

Complexity Breakdown

• Slot Counting: Time O(n), Space O(1).
• Stack-Based: Time O(n), Space O(n).

Slot counting is the leaner choice.

Key Takeaways

• Slot Counting: Track capacity—brilliant!
• Stack-Based: Build and collapse—clear!
• Python: Strings and logic shine—see [Python Basics](/python/basics).
• Trees: Preorder reveals structure.

Final Thoughts: Verify the Tree

LeetCode 331: Verify Preorder Serialization of a Binary Tree in Python is a tree-validation delight. The slot-counting solution offers speed and elegance, while stack-based provides a tangible process. Want more tree challenges? Try LeetCode 144: Binary Tree Preorder Traversal or LeetCode 297: Serialize and Deserialize Binary Tree. Ready to check? Head to Solve LeetCode 331 on LeetCode and validate that string today!