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.
"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 <= 104preorder consist of integers in the range [0, 100] and '#' separated by commas ','.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.
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).
The code uses strtok to tokenize the input string by commas. It starts with 1 available slot and decrements the slot count for each node. Non-null nodes (integers) add two slots, while null nodes ('#') simply use up a slot. If slots go negative at any point, the serialization is invalid. Finally, check all slots are used up.
Time Complexity: O(n), where n is the length of the preorder string, as we are iterating through the nodes once.
Space Complexity: O(1), with no additional data structures used.
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.
This C code uses strtok for splitting and maintains a count 'diff' (similar to slots) decrementing for nodes and adjusting according to whether nodes are null or not.
Time Complexity: O(n), parsing each node once.
Space Complexity: O(1), with only integer variables used for tracking.
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.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Using Slot Management | Time Complexity: O(n), where n is the length of the preorder string, as we are iterating through the nodes once. |
| Simulate Stack-Based Preorder Traversal | Time Complexity: O(n), parsing each node once. |
| Stack | — |
| 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. |
Verify Preorder Serialization of a Binary Tree | Leetcode 331 | Live coding session 🔥🔥🔥 • Coding Decoded • 5,062 views views
Watch 9 more video solutions →Practice Verify Preorder Serialization of a Binary Tree with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor