Watch 10 video solutions for Verify Preorder Serialization of a Binary Tree, a medium level problem involving String, Stack, Tree. This walkthrough by NeetCode has 128,074 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 node values and # represents null. The task is to verify whether this serialization could represent a valid binary tree without reconstructing the tree.
Approach 1: Slot Management (O(n) time, O(1) space)
This approach treats the tree as a system of available child slots. A valid binary tree starts with one slot for the root. When you process a node from the preorder string, it consumes one slot. If the node is not #, it creates two new slots for its children. Iterate through the tokens using split(',') and update the slot count accordingly. If slots ever become negative, the serialization is invalid. At the end, exactly zero slots must remain. This method works because preorder traversal strictly follows parent-before-child ordering, allowing you to track structure without building the actual binary tree. It is the most efficient and commonly expected interview solution.
Approach 2: Simulate Stack-Based Preorder Traversal (O(n) time, O(n) space)
This approach simulates how preorder traversal collapses completed subtrees. Use a stack to store nodes while scanning tokens from left to right. Whenever the pattern node,#,# appears on top of the stack, it represents a fully processed subtree. Pop the two # markers and their parent node, then push a single # to represent the collapsed subtree. Continue processing until no more reductions are possible. If the serialization is valid, the stack should end with a single #. This method closely mirrors how recursive traversal finishes processing a subtree and is intuitive if you think in terms of traversal simulation.
Both approaches rely on parsing the preorder string efficiently using basic string operations. The key idea is validating structure rather than reconstructing nodes.
Recommended for interviews: The slot management approach is the optimal solution. It runs in O(n) time with O(1) extra space and demonstrates a strong understanding of tree structure invariants. The stack simulation method is also acceptable and shows how preorder traversal behaves, but the slot technique is cleaner and usually what interviewers expect.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Slot Management | O(n) | O(1) | Best general solution. Minimal memory and fastest validation of preorder structure. |
| Stack-Based Preorder Simulation | O(n) | O(n) | Useful for understanding subtree completion during traversal or when simulating recursion. |