Verify preorder serialization of a binary tree

String Stack Tree Binary Tree

47.1% acceptance

Jan 12, 2026

2453

132

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.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn is_valid_serialization(preorder: String) -> bool {
    let nodes: Vec<&str> = preorder.split(',').collect();
    let mut slots = 1;
    
    for node in nodes {
      slots -= 1;
      if slots < 0 {
        return false;
      }
      if node != "#" {
        slots += 2;
      }
    }
    
    slots == 0
  }
}