#331

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Verify Preorder Serialization of a Binary Tree

Determine if a given string correctly represents a binary tree preorder traversal using state tracking and slot counting techniques.

string stack tree binary tree

Problem Statement

You are given a string representing a preorder serialization of a binary tree, where each non-null node is a number and null nodes are represented by '#'. Nodes are separated by commas. Determine whether this serialization correctly represents a valid binary tree without reconstructing it.

For example, the string "9,3,4,#,#,1,#,#,2,#,6,#,#" represents a binary tree where '#' indicates a null child. Return true if the given string follows the rules of preorder traversal serialization. Otherwise, return false. Constraints: the string length is between 1 and 10^4, and node values are integers from 0 to 100 separated by commas.

Examples

Example 1

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

Output: true

Example details omitted.

Example 2

Input: preorder = "1,#"

Output: false

Example details omitted.

Example 3

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

Output: false

Example details omitted.

Constraints

1 <= preorder.length <= 104
preorder consist of integers in the range [0, 100] and '#' separated by commas ','.

Solution Approach

Slot Counting Method

Initialize a slot count as 1 for the root. Traverse the preorder string by splitting on commas. For each node, decrement a slot. If the node is not '#', increment slots by 2. If at any point slots become negative, return false. At the end, return true if slots equal zero. This approach simulates tree growth without building the tree.

Stack-Based Simulation

Use a stack to track nodes and their child expectations. Push nodes onto the stack until encountering '#'. When two consecutive '#' are seen on top of the stack, pop the completed subtree and continue. If the stack is empty before processing all nodes, the serialization is invalid. This method mirrors actual traversal logic and detects structural errors early.

Early Termination Optimization

Combine slot counting with immediate failure detection. While iterating, if slots drop below zero, return false immediately. This prevents unnecessary processing for obviously invalid sequences. It leverages the primary failure mode of invalid preorder serialization and optimizes runtime for long strings.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) where n is the number of nodes in the preorder string, as each node is visited once. Space complexity is O(1) for slot counting or O(n) for stack-based simulation, depending on whether explicit stack storage is used.

What Interviewers Usually Probe

Can you verify the serialization without reconstructing the binary tree?
What happens if the preorder string has extra or missing nodes?
How do you track the number of available slots during traversal?

Common Pitfalls or Variants

Common pitfalls

Failing to handle consecutive null nodes correctly in the slot tracking method.
Not decrementing slots before checking for early termination, leading to false positives.
Attempting to reconstruct the tree unnecessarily, increasing space usage and complexity.

Follow-up variants

Verify postorder serialization of a binary tree using a similar slot counting approach.
Validate a binary tree serialization with different null markers, e.g., 'X' instead of '#'.
Check serialization for n-ary trees by adjusting slot increments for variable number of children.

FAQ

What is the main idea behind verifying preorder serialization of a binary tree?

The main idea is to track available slots for nodes, incrementing for non-null nodes and decrementing for each node encountered, ensuring the final slots count is zero.

Can this problem be solved without building the binary tree?

Yes, using slot counting or a stack simulation, you can validate the serialization directly from the string without reconstructing the tree.

What should I do if I encounter consecutive '#' symbols?

Consecutive '#' symbols indicate null children; decrement slots accordingly and use stack or slot rules to detect completed subtrees or invalid sequences.

How does GhostInterview help detect common mistakes?

It simulates both slot counting and stack approaches, highlighting early negative slot counts or invalid subtree completions, preventing structural errors.

Are there variants of this problem I should be aware of?

Yes, variants include postorder serialization verification, using different null markers, or extending the pattern to n-ary trees with adjusted slot rules.

terminal

Solution

Solution 1: Stack

We split the string `preorder` into an array by commas, then traverse the array. If we encounter two consecutive `'#'` and the third element is not `'#'`, we replace these three elements with a single `'#'`. This process continues until the array traversal is complete.

1

2

3

4

5

6

7

8

9

class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        stk = []
        for c in preorder.split(","):
            stk.append(c)
            while len(stk) > 2 and stk[-1] == stk[-2] == "#" and stk[-3] != "#":
                stk = stk[:-3]
                stk.append("#")
        return len(stk) == 1 and stk[0] == "#"

Continue Practicing

#297 serialize and deserialize binary tree #257 binary tree paths #449 serialize and deserialize bst