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:&nbsp;You are not allowed to reconstruct the tree.

&nbsp;
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

&nbsp;
Constraints:


	1 &lt;= preorder.length &lt;= 104
	preorder consist of integers in the range [0, 100] and '#' separated by commas ','.


class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        nodes = preorder.split(',')
        counter=1
        for i, node in enumerate(nodes):
            if node != '#':
                counter+=1
            else:
                if counter <= 1 and i != len(nodes) - 1:
                    return False
                counter-=1
        return counter == 0
class Solution {
    public boolean isValidSerialization(String preorder) {
        String[] strs = preorder.split(",");
        //In starting we have one vacany for root
        int vacancy = 1;
        
        for(String str : strs){
            
            if(--vacancy < 0 ) return false;
            
            // whenever we encounter a new node vacancy decreases by 1 and  left and right two vacancy for                   that node will added in total
            if(!str.equals("#"))            
                vacancy += 2;
           
        }
        
        
        return vacancy == 0;
        
    }
}
class Solution {
public:
    bool isValidSerialization(string preorder) {
        stringstream s(preorder);
        string str;
        int slots=1;
        while(getline(s, str, ',')) {
            if(slots==0) return 0;
            if(str=="#") slots--;
            else slots++;
        }
        return slots==0;
    }
};
/**
 * @param {string} preorder
 * @return {boolean}
 */
var isValidSerialization = function(preorder) {
    let balance = 1
    for(const node of preorder.split(','))
        if (balance > 0)
            if (node === '#') --balance
            else ++balance
        else return false
    return balance < 1
}
Verify Preorder Serialization of a Binary Tree