# Verify Preorder Serialization Of A Binary Tree Problem

## Description

LeetCode Problem 331.

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:

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

Example 2:

``````1
2
Input: preorder = "1,#"
Output: false
``````

Example 3:

``````1
2
Input: preorder = "9,#,#,1"
Output: false
``````

Constraints:

• 1 <= preorder.length <= 10^4
• preorder consist of integers in the range [0, 100] and ‘#’ separated by commas ‘,’.

## Sample C++ Code

We use nodes to count the nodes we are allowed to have next. Every time we get a new node we decrease nodes, if we got below zero it’s false. If we get a non-null node, we can have after it two more nodes. At the end, we are supposed to end up with nodes == 0, otherwise the tree is not good.

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
bool isValidSerialization(string preorder) {
stringstream ss(preorder);
string curr;
int nodes = 1;
while (getline(ss, curr, ',')) {
nodes--;
if (nodes < 0) return false;
if (curr != "#") nodes += 2;
}
return nodes == 0;
}
};
``````