Verify Preorder Serialization of a Binary Tree
MedPrompt
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: trueExample 2:
Input: preorder = "1,#"
Output: falseExample 3:
Input: preorder = "9,#,#,1"
Output: false
Constraints:
1 <= preorder.length <= 104preorderconsist of integers in the range[0, 100]and'#'separated by commas','.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses a stack to iteratively validate the preorder string. The main idea is to treat a (number, #, #) sequence as a complete subtree that can be 'reduced' or replaced by a single '#' from its parent's perspective. By processing the nodes and performing these reductions, a valid serialization should ultimately simplify to a single '#', representing the entire valid tree.
Algorithm
- Split the input
preorderstring by commas to get an array ofnodes. - Initialize an empty
stackof strings. - Iterate through each
nodein thenodesarray:- If the
nodeis a number, push it onto thestack. - If the
nodeis'#':- Repeatedly check if the top of the stack is also
'#'. This signifies anumber, #, #pattern. - If it is, pop the
'#' and the preceding number from the stack. This 'reduces' the subtree to a single conceptual'#'. - After the reduction loop, push the current
'#' onto the stack.
- Repeatedly check if the top of the stack is also
- If the
- After iterating through all nodes, a valid serialization will result in the stack containing exactly one element:
'#'. - If the final stack state is
['#'], returntrue; otherwise, returnfalse.
Walkthrough
We can simulate the tree validation process using a stack. We iterate through the nodes provided in the preorder string. When we encounter a number, it represents a new subtree root, so we push it onto the stack. When we encounter a null marker (#), it signifies the end of a branch.
A key observation is that a node followed by two null markers (e.g., 4,#,#) forms a complete leaf node from its parent's point of view. This entire structure can be conceptually replaced by a single #. We implement this by checking if the top of our stack is a # when we see a new #. If so, we pop the existing # and its parent number, effectively reducing them. We repeat this until the condition is no longer met. Finally, we push the current # onto the stack.
If the preorder string is valid, this process will consume all nodes and leave a single # on the stack at the end. Any other final state of the stack indicates an invalid serialization.
import java.util.Stack; class Solution { public boolean isValidSerialization(String preorder) { String[] nodes = preorder.split(","); Stack<String> stack = new Stack<>(); for (String node : nodes) { if (node.equals("#")) { // Reduce "number,#,#" to "#" while (!stack.isEmpty() && stack.peek().equals("#")) { stack.pop(); // Pop the first '#' // After a '#', there must be a number to form a pair if (stack.isEmpty() || stack.peek().equals("#")) { return false; } stack.pop(); // Pop the number } stack.push("#"); } else { stack.push(node); } } // A valid serialization will be reduced to a single '#' return stack.size() == 1 && stack.peek().equals("#"); }}Complexity
Time
O(N), where N is the number of nodes. The string split operation takes O(L) time (L is string length, proportional to N). Each node is pushed onto the stack once. The inner `while` loop might seem to add complexity, but each element is popped at most once, leading to an amortized O(1) time per node.
Space
O(N), where N is the number of nodes in the serialization. This is due to storing the split string in an array and the space used by the stack, which in the worst-case (a skewed tree) can hold O(N) elements.
Trade-offs
Pros
Avoids recursion, which can prevent stack overflow errors on deeply skewed trees.
The logic directly simulates the hierarchical nature of the tree structure.
Cons
Requires O(N) extra space for the stack, which can be significant for large inputs.
The logic involving the reduction loop can be slightly more complex to reason about than a direct counting method.
Solutions
Solution
class Solution {public boolean isValidSerialization(String preorder) { List<String> stk = new ArrayList<>(); for (String s : preorder.split(",")) { stk.add(s); while (stk.size() >= 3 && stk.get(stk.size() - 1).equals("#") && stk.get(stk.size() - 2).equals("#") && !stk.get(stk.size() - 3).equals("#")) { stk.remove(stk.size() - 1); stk.remove(stk.size() - 1); stk.remove(stk.size() - 1); stk.add("#"); } } return stk.size() == 1 && stk.get(0).equals("#"); }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.