Move from brute-force thinking to an efficient approach using stack strategy.
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 summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Stack · Tree
"9,3,4,#,#,1,#,#,2,#,6,#,#"
"1,#"
"9,#,#,1"
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #331: Verify Preorder Serialization of a Binary Tree
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("#");
}
}
// Accepted solution for LeetCode #331: Verify Preorder Serialization of a Binary Tree
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] == "#"
}
# Accepted solution for LeetCode #331: Verify Preorder Serialization of a Binary Tree
class Solution:
def isValidSerialization(self, preorder: str) -> bool:
stk = []
for c in preorder.split(","):
stk.append(c)
while len(stk) > 2 and stk[-1] == stk[-2] == "#" and stk[-3] != "#":
stk = stk[:-3]
stk.append("#")
return len(stk) == 1 and stk[0] == "#"
// Accepted solution for LeetCode #331: Verify Preorder Serialization of a Binary Tree
struct Solution;
impl Solution {
fn is_valid_serialization(preorder: String) -> bool {
let mut stack: Vec<char> = vec![];
for tok in preorder.split(',') {
if tok == "#" {
while let Some('#') = stack.last() {
stack.pop();
if stack.pop().is_none() {
return false;
};
}
stack.push('#');
} else {
stack.push('$');
}
}
stack == vec!['#']
}
}
#[test]
fn test() {
let preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#".to_string();
let res = true;
assert_eq!(Solution::is_valid_serialization(preorder), res);
let preorder = "1,#".to_string();
let res = false;
assert_eq!(Solution::is_valid_serialization(preorder), res);
let preorder = "9,#,#,1".to_string();
let res = false;
assert_eq!(Solution::is_valid_serialization(preorder), res);
let preorder = "1,#,#,#,#".to_string();
let res = false;
assert_eq!(Solution::is_valid_serialization(preorder), res);
}
// Accepted solution for LeetCode #331: Verify Preorder Serialization of a Binary Tree
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] === '#';
}
Use this to step through a reusable interview workflow for this problem.
For each element, scan left (or right) to find the next greater/smaller element. The inner scan can visit up to n elements per outer iteration, giving O(n²) total comparisons. No extra space needed beyond loop variables.
Each element is pushed onto the stack at most once and popped at most once, giving 2n total operations = O(n). The stack itself holds at most n elements in the worst case. The key insight: amortized O(1) per element despite the inner while-loop.
Review these before coding to avoid predictable interview regressions.
Wrong move: Pushing without popping stale elements invalidates next-greater/next-smaller logic.
Usually fails on: Indices point to blocked elements and outputs shift.
Fix: Pop while invariant is violated before pushing current element.
Wrong move: Recursive traversal assumes children always exist.
Usually fails on: Leaf nodes throw errors or create wrong depth/path values.
Fix: Handle null/base cases before recursive transitions.