# Verify Preorder Serialization of a Binary Tree

# 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:

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

# Example 2:

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


class Solution:
    def isValidSerialization(self, preorder):
        stack, count = [], 0
        for item in preorder.split(','):
            stack.append(item)
            count += 1
            while count > 1 and stack[-1] == '#' and stack[-2] == '#':
                stack.pop()
                stack.pop()
                if not stack: return False
                stack[-1] = '#'
                count -= 2
        return (len(stack) == 1 and stack[0] == '#')

        # # base case
        # # if not preorder:
        # #     return True
        # # # use stack to store visited nodes
        # # stack = []
        # # for node in preorder.split(','):
        # #     while node == '#' and stack and stack[-1] == '#':
        # #         stack.pop()
        # #         if not stack:
        # #             return False
        # #         stack.pop()
        # #     stack.append(node)
        # # return stack == ['#']

if __name__ == '__main__':
    sol = Solution()
    preorder = "9,#,#,1"
    print(sol.isValidSerialization(preorder))