One way to serialize a binary tree is to use pre-order 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 #.


     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #


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, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.

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".

Example 1:


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

Example 2:


Input: "1,#"
Output: false


Example 3:


Input: "9,#,#,1"
Output: false

Difficulty: interview

Starter code:

class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        

Solutions:
class Solution(object):
     def isValidSerialization(self, preorder):
         """
         :type preorder: str
         :rtype: bool
         """
         # remember how many empty slots we have
         # non-null nodes occupy one slot but create two new slots
         # null nodes occupy one slot
         
         p = preorder.split(',')
         
         #initially we have one empty slot to put the root in it
         slot = 1
         for node in p:
             
             # no empty slot to put the current node
             if slot == 0:
                 return False
                 
             # a null node?
             if node == '#':
                 # ocuppy slot
                 slot -= 1
             else:
                 # create new slot
                 slot += 1
         
         #we don't allow empty slots at the end
         return slot==0

class Solution:
     def isValidSerialization(self, preorder):
         """
         :type preorder: str
         :rtype: bool
         """
         if not preorder:
             return False
         
         nodes = preorder.split(',')
         stack = [0] if nodes[0] != '#' else []
         dt = {0:2}
         i = 1
         
         while stack and i < len(nodes):
             dt[stack[-1]] -= 1
             if dt[stack[-1]] == 0:
                 stack.pop()
             if nodes[i] != '#':
                 stack.append(i)
                 dt[i] = 2
             i = i + 1
         
         return not stack and i == len(nodes)
         
         


class Solution:
     def isValidSerialization(self, preorder):
         new_preorder = preorder 
         for i in range (len(new_preorder)-1,0,-1):
             if (new_preorder[i] != '#' and new_preorder[i] != ',') and (new_preorder[i-1] != '#' and new_preorder[i-1] != ','):
                 preorder = preorder[:i] + preorder[i+1:]
                 #print(i)
         print(preorder)
         #print(int(((len(preorder)/2)+1)/2))
         num = 0
         sharp = 0
         for i in range (0 , len(preorder)):
             print((num,sharp))
             if sharp > num:
                 return False
             elif preorder[i] == '#':
                 #print(num,sharp)
                 sharp += 1
                 if sharp == num+1 and num == int(((len(preorder)/2)+1)/2):
                     return True
             elif preorder[i] != ',':
                 num += 1
                 
         print((num,sharp))
         if num != sharp - 1:
             return False
         """
         :type preorder: str
         :rtype: bool
         """


class Solution:
     def isValidSerialization(self, preorder):
         """
         :type preorder: str
         :rtype: bool
         """
         arr = preorder.split(',')
         k = len(arr)
         for _ in range(k):
             print(arr)
             if arr==['#']:
                 return True
             newArr = []
             i = 0
             while i < len(arr):
                 if i < len(arr)-2 and arr[i].isdigit() and arr[i+1:i+3] == ['#','#']:
                     newArr += ['#']
                     i += 3
                 else:
                     newArr += [arr[i]]
                     i += 1
             arr = newArr
         return False


class Solution:
     def isValidSerialization(self, preorder):
         """
         :type preorder: str
         :rtype: bool
         """
         preorder = preorder.split(',')
 
         if preorder[0] == '#':
             return len(preorder) == 1
 
         s = []
 
         curr = preorder[0]
         on_left = True
 
         for i in range(1, len(preorder)):
             if not curr:
                 return False
 
             e = preorder[i]
 
             if e != '#':
                 if on_left:
                     s.append(curr)
 
                 curr = e
                 on_left = True
             else:
                 if not on_left:
                     curr = s.pop() if len(s) > 0 else None
 
                 on_left = False
 
         return curr is None

class Solution:
     def isValidSerialization(self, preorder):
         """
         :type preorder: str
         :rtype: bool
         """
         # '' valid or not?
         if len(preorder) < 1:
             return False
 
         stack = []
         for s in preorder.split(','):
             stack.append(False)
             if s == '#':
                 # remove pairing left branch
                 while len(stack) > 2 and stack[-2]:
                     stack.pop()
                     stack.pop()
                     stack.pop()
                 else:
                     stack.append(True)
 
         return stack == [False, True]        

class Solution:
     def isValidSerialization(self, preorder):
         """
         :type preorder: str
         :rtype: bool
         """
         if not preorder:
             return True
         arr = preorder.split(',')
         s = []
         for a in arr:
             s.append(a)
             while len(s)>=3 and s[-1]=='#' and s[-2]=='#' and s[-3]!='#':
                 s.pop()
                 s.pop()
                 s.pop()
                 s.append('#')
         if s==['#']:
             return True
         return False


class Solution:
     def isValidSerialization(self, preorder):
         """
         :type preorder: str
         :rtype: bool
         """
         preorder = preorder.split(',')
 
         if preorder[0] == '#':
             return len(preorder) == 1
 
         s = []
 
         curr = preorder[0]
         on_left = True
         finish = False
 
         for i in range(1, len(preorder)):
             if not curr:
                 return False
 
             e = preorder[i]
 
             if e != '#':
                 s.append((curr, on_left))
                 curr = e
                 on_left = True
                 finish = False
             else:
                 if not on_left:
                     curr = None
                     finish = True
 
                     while len(s) and not on_left:
                         curr, on_left = s.pop()
 
                     if curr and not on_left:
                         curr = None
 
                 on_left = False
 
         return finish

class Solution:
     def isValidSerialization(self, preorder):
         """
         :type preorder: str
         :rtype: bool
         """
         stack,preorder = [],preorder.split(',')
         top = -1
         for s in preorder:
             stack.append(s)
             top += 1
             while(self.endsWithTwoHashes(stack,top)):
                 h,top = stack.pop(),top-1
                 h,top = stack.pop(),top-1
                 if top < 0: return False
                 stack[-1] = '#'
                 #h = stack.pop()
                 #stack.append('#')
         return len(stack) == 1 and stack[0]=='#'
 
     def endsWithTwoHashes(self,stack,top):
         if top<1:
             return False
         if stack[top]=='#' and stack[top-1]=='#':
             return True
         return False

class Solution:
     def isValidSerialization(self, preorder):
         """
         :type preorder: str
         :rtype: bool
         """   
         preorder, first = preorder.split(","), preorder.split(",")
         def backward(index):
             if index >= len(preorder) or index < 0: return 
             if index+1<len(preorder) and preorder[index+1] == preorder[index] == "#" and index-1 >= 0 and preorder[index-1] != "#":
                 preorder.pop(index)
                 preorder.pop(index)
                 preorder[index-1] = "#"
                 backward(index-2)
             else: backward(index+1)
         backward(0)
         return True if (preorder != first and preorder == ["#"]) or (preorder == first == ["#"]) else False