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

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Tree algorithms

Data structures

String algorithms

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

Solutions:
class Solution(object):

	def isValidSerialization(self, preorder):
		p = preorder.split(',')
		slot = 1
		for node in p:
			if slot == 0:
				return False
			if node == '#':
				slot -= 1
			else:
				slot += 1
		return slot == 0


class Solution:

	def isValidSerialization(self, preorder):
		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(preorder)
		num = 0
		sharp = 0
		for i in range(0, len(preorder)):
			print((num, sharp))
			if sharp > num:
				return False
			elif preorder[i] == '#':
				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


class Solution:

	def isValidSerialization(self, preorder):
		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):
		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):
		if len(preorder) < 1:
			return False
		stack = []
		for s in preorder.split(','):
			stack.append(False)
			if s == '#':
				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):
		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):
		(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] = '#'
		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):
		(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