Grokking 226

class Solution {
    public boolean isValidSerialization(String preorder) {
        // Initially, there is one empty slot
        int emptyLeaf = 1;

        for (int i = 0; i < preorder.length(); i++) {
            if (emptyLeaf == 0) return false;

            char c = preorder.charAt(i);
            if (c == ',') {
                continue;
            }

            // If the next token is not ',' or '#' then it's a node, add 2 slots for 2 children of that node
            if (c != '#') {
                emptyLeaf += 2;
                int j = i;
                while (j < preorder.length() && preorder.charAt(j) != ',') j++;
                i = j - 1;
            }

            // Whether the token is '#' or a node, it takes 1 empty slot
            emptyLeaf -= 1;
            if (emptyLeaf < 0) return false;
        }
        return emptyLeaf == 0;
    }
}