Valid Binary Tree Serialization

You are given a string representing the preorder traversal serialization of a binary tree. Each node is represented by a value and null nodes are denoted by the character #. The nodes are separated by commas.

The serialization is valid if and only if it represents a correct binary tree structure. In particular, we use the following idea: Let \(\text{capacity}\) be initially set to 1 (representing the slot for the root). For every node encountered, reduce \(\text{capacity}\) by 1 (since the node occupies one slot). If the node is not a null node (i.e. not #), then it generates two additional slots for its children, so increase \(\text{capacity}\) by 2. The serialization is valid if and only if \(\text{capacity} = 0\) after processing all nodes, and at no point does \(\text{capacity}\) become negative.

For example, the serialization "9,3,4,#,#,1,#,#,2,#,6,#,#" is valid, whereas "1,#" is not valid.

inputFormat

The input consists of a single line containing a comma-separated string that represents the preorder traversal of a binary tree.

outputFormat

Print True if the serialization is valid, and False otherwise.

9,3,4,#,#,1,#,#,2,#,6,#,#

True