# LeetCode: 331. Verify Preorder Serialization of a Binary Tree

**The Problem**

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

`'#'`

.**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.

```
Input: preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#"
Output: true
```

**Constraints:**

`1 <= preorder.length <= 10`

^{4}`preorder`

consist of integers in the range`[0, 100]`

and`'#'`

separated by commas`','`

.

**Solution**

We chose an iterative approach to solve the problem. When we evaluated our solution on the LeetCode platform, here are the results:

Here's the code that led us to this result.

```
bool isValidSerialization(string preorder) {
stringstream str(preorder);
string node;
int count = 1;
while(getline(str, node, ',')){
--count;
if(count < 0) return false;
if(node != "#") count = count + 2;
}
return count == 0;
}
```

Here's a simplified explanation:

- It starts by splitting the
`preorder`

string into individual nodes using a comma (',') as the delimiter. - It initializes a variable
`count`

to 1. This variable represents the number of available slots for nodes in the tree.

It iterates through the nodes one by one:

- For each node encountered, it decrements
`count`

by 1. - If
`count`

becomes negative at any point, it means there are more nodes in the traversal than slots available, which is not valid. In this case, it returns`false`

. - If the node is not a '#' (representing a valid node), it means there are two more slots available for child nodes, so it increments
`count`

by 2.

- After processing all nodes, it checks if
`count`

is back to 0. If it is, it means the traversal is valid, and it returns`true`

; otherwise, it returns`false`

.