# Short C++ code with explanations (single pass, no tockenize, no stack, no recursion)

• There is not any totally new idea regarding the algorithm in the code below. I just thought that it might be helpful to mention a truly single-pass and easy to understand C++ code with a bit different explanation.

If you start with the shortest possible valid input string (`"#"`), you clearly see that you have `0` non-null nodes and `1` null node. Every time you want to add a new non-null node to the tree, you need to add two more null nodes (e.g. `"1##"`, `"12###"` and `"1#2##"`). So there must always be exactly one more null node in the whole tree. If you start with a simple counter and scan the input string from left to right by incrementing the counter for every non-null node and decrementing it for every null node, it can be proven (by induction) that:

• the input string is valid if and only if the counter is equal to `-1` at the end,
• if the counter gets negative before reaching the end, the input string is not valid,
• if the counter gets zero, it means you're done with traversing a left subtree.
``````bool isValidSerialization(std::string preorder) {
preorder.push_back(','); // no harm as we know the input string is in the correct format
int i = 0, cnt = 0; // increment 'cnt' for each non-null node & decrement for each null (#) node
while (i < preorder.length() && cnt > -1) {
if (preorder[i] == '#') { cnt--; i += 2; } // skip the next ',' in the input
else if (std::isdigit(preorder[i])) { i++; } // continue until reaching the end of digits of the non-null node
else if (preorder[i] == ',') { cnt++; i++; } // the last node can't be a null node, so increment the counter
else { return false; } // a wrong character in the input string
}
return cnt == -1 && i >= preorder.length();
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.