Verify Preorder Serialization of a Binary Tree - Solution & Explanation

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.