331. Verify Preorder Serialization Solution

The problem

One way to serialize a binary tree is to use preorder traversal. When we encounter a non-null node, we record the node's value. If it is a null node, we record using a sentinel value such as '#'.

For example, the above binary tree can be serialized to the string "9,3,4,#,#,1,#,#,2,#,6,#,#", where '#' represents a null node.

Given a string of comma-separated values preorder, return true if it is a correct preorder traversal serialization of a binary tree.

It is guaranteed that each comma-separated value in the string must be either an integer or a character '#' representing null pointer.

You may assume that the input format is always valid.

For example, it could never contain two consecutive commas, such as "1,,3".

Note: You are not allowed to reconstruct the tree.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

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

Approach overview

Problem Overview: You receive a comma-separated preorder traversal of a binary tree where numbers represent nodes and # represents null pointers. The task is to verify whether this serialization could represent a valid binary tree without reconstructing the tree.

The preorder format follows the rule root -> left -> right. A valid binary tree consumes and produces child slots as nodes appear. If the serialization ever tries to use a slot that doesn't exist, or leaves unused slots at the end, the structure is invalid.

Approach 1: Using Slot Management (O(n) time, O(1) space)

This is the most efficient approach and avoids building the tree entirely. Think of each node as occupying a slot in the tree. Start with one slot for the root. Every token in the preorder string consumes one slot. If the token is a number (a real node), it creates two new slots for its children. If it is #, it creates no new slots because null nodes have no children. Iterate through the tokens and update the slot count accordingly.

If slots ever drop below zero, the serialization tries to place a node where no position exists, which means the structure is invalid. After processing all tokens, the slot count must be exactly zero. This approach runs in O(n) time because each token is processed once, and O(1) space since only an integer counter is maintained. The method relies on understanding binary tree structure rather than simulating traversal. It commonly appears in problems involving tree validation and preorder properties.

Approach 2: Simulate Stack-Based Preorder Traversal (O(n) time, O(n) space)

This approach mimics how preorder serialization collapses completed subtrees. Iterate through tokens and push them onto a stack. Whenever the top of the stack forms the pattern node, #, #, that subtree is fully processed. Replace the pattern with a single #, representing the completed subtree as a null child of its parent.

Continue collapsing while this pattern exists. If the serialization is valid, the entire stack eventually reduces to a single #. This technique explicitly models subtree completion and works well if you prefer a structural simulation over arithmetic reasoning. The time complexity remains O(n) because each element is pushed and popped at most once, while the stack requires O(n) space. The implementation uses common operations seen in stack problems and token parsing from string inputs.

Recommended for interviews: The slot management method is what most interviewers expect. It demonstrates that you understand how binary tree nodes expand and consume child positions. The stack approach is also valid and easier to reason about visually, but the slot counting technique is cleaner, uses constant space, and signals deeper familiarity with preorder properties in binary tree problems.

Approach 1: Using Slot Management

The idea is to track available slots in the binary tree. Initially, we start with one slot for the root. For each node, we consume a slot. If the node is non-null, it adds two more slots (one for each child). A null node ('#') does not add any slots. The binary tree is valid if, at the end of processing all nodes, all slots are exactly filled (i.e., zero slots remaining).

Python

class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        slots = 1
        nodes = preorder.split(',')
        for node in nodes:
            slots -= 1
            if slots < 0:
                return False
            if node != '#':
                slots += 2
        return slots == 0

# Example Usage
solution = Solution()
print(solution.isValidSerialization("9,3,4,#,#,1,#,#,2,#,6,#,#"))

Java

public class Solution {
    public boolean isValidSerialization(String preorder) {
        int slots = 1;
        String[] nodes = preorder.split(",");
        for (String node : nodes) {
            slots--;
            if (slots < 0) return false;
            if (!node.equals("#")) slots += 2;
        }
        return slots == 0;
    }
    public static void main(String[] args) {
        Solution solution = new Solution();
        String preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#";
        System.out.println(solution.isValidSerialization(preorder));
    }
}

C++

#include <sstream>
#include <string>
#include <iostream>
using namespace std;

bool isValidSerialization(string preorder) {
    int slots = 1;
    stringstream ss(preorder);
    string node;
    while (getline(ss, node, ',')) {
        slots--;
        if (slots < 0) return false;
        if (node != "#") slots += 2;
    }
    return slots == 0;
}

int main() {
    string preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#";
    cout << (isValidSerialization(preorder) ? "true" : "false");
    return 0;
}

JavaScript

function isValidSerialization(preorder) {
    let slots = 1;
    const nodes = preorder.split(',');
    for (let node of nodes) {
        slots--;
        if (slots < 0) return false;
        if (node !== '#') slots += 2;
    }
    return slots === 0;
}

// Example usage
console.log(isValidSerialization("9,3,4,#,#,1,#,#,2,#,6,#,#"));

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool isValidSerialization(char * preorder) {
    int slots = 1;
    for (char *ptr = strtok(preorder, ","); ptr; ptr = strtok(NULL, ",")) {
        slots--;
        if (slots < 0) {
            return false;
        }
        if (strcmp(ptr, "#") != 0) {
            slots += 2;
        }
    }
    return slots == 0;
}

int main() {
    char preorder[] = "9,3,4,#,#,1,#,#,2,#,6,#,#";
    printf("%s\n", isValidSerialization(preorder) ? "true" : "false");
    return 0;
}

using System;

public class Solution {
    public bool IsValidSerialization(string preorder) {
        int slots = 1;
        string[] nodes = preorder.Split(',');
        foreach (string node in nodes) {
            slots--;
            if (slots < 0) return false;
            if (node != "#") slots += 2;
        }
        return slots == 0;
    }

    public static void Main() {
        Solution solution = new Solution();
        string preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#";
        Console.WriteLine(solution.IsValidSerialization(preorder));
    }
}

In this Python implementation, the preorder string is split into nodes. The slots management is handled as per the provided logic: decrementing for each node and incrementing if the node is not null.

Complexity

Time Complexity: O(n) for iterating over the nodes.
Space Complexity: O(n), due to the list of nodes created after splitting the string.

Try this approach in the editor

Approach 2: Simulate Stack-Based Preorder Traversal

This approach involves simulating a stack-based tree traversal. The idea is to treat each "open bracket" as requiring nodes and each "close bracket" as completing them. We aim to manage the state of openings and closures using integers, representing how many nodes are expected at any point in the traversal.

Python

class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        diff = 1
        nodes = preorder.split(',')
        for node in nodes:
            diff -= 1
            if diff < 0:
                return False
            if node != '#':
                diff += 2
        return diff == 0

# Example Usage
solution = Solution()
print(solution.isValidSerialization("9,3,4,#,#,1,#,#,2,#,6,#,#"))

Java

public class Solution {
    public boolean isValidSerialization(String preorder) {
        int diff = 1;
        String[] nodes = preorder.split(",");
        for (String node : nodes) {
            if (--diff < 0) return false;
            if (!node.equals("#")) diff += 2;
        }
        return diff == 0;
    }
    public static void main(String[] args) {
        Solution solution = new Solution();
        String preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#";
        System.out.println(solution.isValidSerialization(preorder));
    }
}

C++

#include <sstream>
#include <string>
#include <iostream>
using namespace std;

bool isValidSerialization(string preorder) {
    int diff = 1;
    stringstream ss(preorder);
    string node;
    while (getline(ss, node, ',')) {
        if (--diff < 0) return false;
        if (node != "#") diff += 2;
    }
    return diff == 0;
}

int main() {
    string preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#";
    cout << (isValidSerialization(preorder) ? "true" : "false");
    return 0;
}

JavaScript

function isValidSerialization(preorder) {
    let diff = 1;
    const nodes = preorder.split(',');
    for (let node of nodes) {
        diff--;
        if (diff < 0) return false;
        if (node !== '#') diff += 2;
    }
    return diff === 0;
}

// Example usage
console.log(isValidSerialization("9,3,4,#,#,1,#,#,2,#,6,#,#"));

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool isValidSerialization(char * preorder) {
    int diff = 1;
    for (char *ptr = strtok(preorder, ","); ptr; ptr = strtok(NULL, ",")) {
        if (--diff < 0) return false;
        if (strcmp(ptr, "#") != 0) diff += 2;
    }
    return diff == 0;
}

int main() {
    char preorder[] = "9,3,4,#,#,1,#,#,2,#,6,#,#";
    printf("%s\n", isValidSerialization(preorder) ? "true" : "false");
    return 0;
}

using System;

public class Solution {
    public bool IsValidSerialization(string preorder) {
        int diff = 1;
        string[] nodes = preorder.Split(',');
        foreach (string node in nodes) {
            if (--diff < 0) return false;
            if (node != "#") diff += 2;
        }
        return diff == 0;
    }

    public static void Main() {
        Solution solution = new Solution();
        string preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#";
        Console.WriteLine(solution.IsValidSerialization(preorder));
    }
}

The Python implementation maintains a shift in expected nodes count, incrementing and decrementing for non-null and null nodes, respectively.

Complexity

Time Complexity: O(n), dictated by node traversal.
Space Complexity: O(n), due to string split operations needed for processing.

Try this approach in the editor

Approach 3: 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.

Finally, we check whether the length of the array is 1 and whether the only element in the array is '#'.

The time complexity is O(n) and the space complexity is O(n), where n is the length of the string preorder.

TypeScript

function isValidSerialization(preorder: string): boolean {
    const stk: string[] = [];
    for (const s of preorder.split(',')) {
        stk.push(s);
        while (stk.length >= 3 && stk.at(-1) === '#' && stk.at(-2) === '#' && stk.at(-3) !== '#') {
            stk.splice(-3, 3, '#');
        }
    }
    return stk.length === 1 && stk[0] === '#';
}

func isValidSerialization(preorder string) bool {
	stk := []string{}
	for _, s := range strings.Split(preorder, ",") {
		stk = append(stk, s)
		for len(stk) >= 3 && stk[len(stk)-1] == "#" && stk[len(stk)-2] == "#" && stk[len(stk)-3] != "#" {
			stk = stk[:len(stk)-3]
			stk = append(stk, "#")
		}
	}
	return len(stk) == 1 && stk[0] == "#"
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Using Slot Management	Time Complexity: O(n) for iterating over the nodes. Space Complexity: O(n), due to the list of nodes created after splitting the string.
Simulate Stack-Based Preorder Traversal	Time Complexity: O(n), dictated by node traversal. Space Complexity: O(n), due to string split operations needed for processing.
Stack	–

Complexity analysis

Approach	Time	Space	When to Use
Slot Management	O(n)	O(1)	Best overall approach. Minimal memory and fastest validation without building the tree.
Stack-Based Subtree Simulation	O(n)	O(n)	Useful when you want to explicitly simulate subtree completion using stack patterns.

Frequently asked questions

Is Verify Preorder Serialization of a Binary Tree easy or hard?

The problem is rated Medium on LeetCode because the optimal solution requires recognizing the slot counting insight. Once the preorder property is understood, the implementation is straightforward and runs in linear time.

Verify Preorder Serialization of a Binary Tree Python/Java solution

Most implementations parse the comma-separated string and apply slot counting. The logic is identical across languages: iterate tokens, decrement slots, and add two slots when encountering a non-null node. Python, Java, C++, C, C#, and JavaScript solutions typically implement this in under 10 lines.

How to solve Verify Preorder Serialization of a Binary Tree in O(n)?

Split the preorder string by commas and track available child slots. Start with one slot for the root. For every token, consume one slot. If the token is a number, add two new slots for its children. If slots ever become negative the serialization is invalid, and a valid serialization must end with exactly zero slots.

What is the best approach for Verify Preorder Serialization of a Binary Tree?

The slot counting (slot management) approach is considered the best solution. Each node consumes one slot, while non-null nodes create two new slots for children. Processing the serialization while tracking available slots validates the structure in O(n) time and O(1) space without reconstructing the tree.

Is Verify Preorder Serialization of a Binary Tree asked at Google/Amazon/Meta?

Tree serialization and validation problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of this question test understanding of preorder traversal, tree structure constraints, and efficient validation without building the full tree.

What data structure is used in Verify Preorder Serialization of a Binary Tree?

The optimal solution uses a simple counter representing available child slots. An alternative approach uses a stack to detect the pattern node, #, # which indicates a completed subtree. Both approaches rely on understanding preorder traversal properties of binary trees.

What is the time complexity of Verify Preorder Serialization of a Binary Tree?

The optimal solution runs in O(n) time where n is the number of tokens in the serialization string. Each token is processed exactly once. Space complexity is O(1) with slot counting or O(n) when using the stack-based subtree simulation approach.

Verify Preorder Serialization of a Binary Tree solution and explanation

The problem

Approach overview

Approach 1: Using Slot Management

Approach 2: Simulate Stack-Based Preorder Traversal

Approach 3: Stack

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Verify Preorder Serialization of a Binary Tree solution and explanation

The problem

Approach overview

Approach 1: Using Slot Management

Approach 2: Simulate Stack-Based Preorder Traversal

Approach 3: Stack

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems