Serialization is to store a tree in an array so that it can be later restored and Deserialization is reading tree back from the array. Now your task is to complete the function serialize which stores the tree into an array A[ ] and deSerialize which deserializes the array to the tree and returns it.
Note: The structure of the tree must be maintained. Multiple nodes can have the same data.
Example 1:
Input:
      1
    /   \
   2     3
Output: 2 1 3
Example 2:
Input:
         10
       /    \
      20    30
    /   \
   40  60
Output: 40 20 60 10 30
Your Task:
The task is to complete two functions serialize which takes the root node of the tree as input and stores the tree into an array and deSerialize which deserializes the array to the original tree and returns the root of it.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
1 <= Number of nodes <= 1000
1 <= Data of a node <= 1000

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3





'''

class Node:

    def __init__(self,val):

        self.data = val

        self.left = None

        self.right = None

'''



#Function to serialize a tree and return a list containing nodes of tree.

def serialize(root, A):

    #code here



#Function to deserialize a list and construct the tree.   

def deSerialize(A):

    #code here

    

Solutions:
from collections import deque

def serialize(root, ans):
	if root is None:
		return ans
	queue = deque()
	queue.append(root)
	while len(queue) != 0:
		size = len(queue)
		for i in range(size):
			node = queue[0]
			queue.popleft()
			if node is None:
				ans.append(None)
				continue
			queue.append(node.left)
			queue.append(node.right)
			ans.append(node.data)
	while ans[-1] is None:
		ans.pop()
	return ans

def deSerialize(arr):
	if len(arr) == 0:
		return None
	queue = deque()
	root = Node(arr[0])
	queue.append(root)
	start = 1
	end = len(arr)
	while len(queue) != 0 and start < len(arr):
		size = len(queue)
		elements_to_extract = size * 2
		end = min(len(arr), start + elements_to_extract)
		rotation = 0
		while start < end:
			node = None
			if arr[start] is not None:
				node = Node(arr[start])
				queue.append(node)
			curr = queue[0]
			if rotation == 0:
				curr.left = node
				rotation = 1
			else:
				curr.right = node
				queue.popleft()
				rotation = 0
			start += 1
	return root


def serialize(root, A):
	q = [root]
	A.append(root)
	while len(q) > 0:
		l = len(q)
		for _ in range(l):
			temp = q[0]
			q.pop(0)
			if temp.left != None:
				q.append(temp.left)
				A.append(temp.left)
			else:
				A.append(None)
			if temp.right != None:
				q.append(temp.right)
				A.append(temp.right)
			else:
				A.append(None)
	return A

def deSerialize(A):
	root = A[0]
	A = A[1:]
	n = len(A)
	st = [root]
	for i in range(n // 2):
		temp = st[0]
		st.pop(0)
		temp.left = A[2 * i]
		temp.right = A[2 * i + 1]
		if A[2 * i] != None:
			st.append(A[2 * i])
		if A[2 * i + 1] != None:
			st.append(A[2 * i + 1])
	return root


def serialize(root, A):
	if not root:
		A.append('#')
		return A
	A.append(root.data)
	serialize(root.left, A)
	serialize(root.right, A)
	return A

def deSerialize(A):
	c = A.pop(0)
	if c == '#':
		return None
	r = Node(c)
	r.left = deSerialize(A)
	r.right = deSerialize(A)
	return r


def serialize(root, A):
	if root is None:
		A.append('#')
		return A
	A.append(root.data)
	serialize(root.left, A)
	serialize(root.right, A)
	return A

def deSerialize(A):
	curr = A.pop(0)
	if curr == '#':
		return None
	node = Node(curr)
	node.left = deSerialize(A)
	node.right = deSerialize(A)
	return node


def serialize(root, A):
	if root is None:
		A.append(-1)
		return
	A.append(root.data)
	serialize(root.left, A)
	serialize(root.right, A)

def deSerialize(A):
	temp = A.pop(0)
	if temp == -1:
		return
	root = Node(temp)
	root.left = deSerialize(A)
	root.right = deSerialize(A)
	return root


class Node:

	def __init__(self, val):
		self.data = val
		self.left = None
		self.right = None

def serialize(root, A):
	if not root:
		A.append(-1)
		return
	A.append(root.data)
	serialize(root.left, A)
	serialize(root.right, A)

def deSerializeUtil(A, i):
	if i[0] >= len(A) or A[i[0]] == -1:
		i[0] += 1
		return None
	node = Node(A[i[0]])
	i[0] += 1
	node.left = deSerializeUtil(A, i)
	node.right = deSerializeUtil(A, i)
	return node

def deSerialize(A):
	i = [0]
	return deSerializeUtil(A, i)


def serialize(root, A):
	if root == None:
		A.append(-1)
		return A
	A.append(root.data)
	serialize(root.left, A)
	serialize(root.right, A)
	return A

def deSerialize(A):
	node = A.pop(0)
	if node == -1:
		return None
	root = Node(node)
	root.left = deSerialize(A)
	root.right = deSerialize(A)
	return root


def serialize(root, A):
	if root == None:
		return
	serialize(root.left, A)
	A.append(root.data)
	serialize(root.right, A)

def solve(A, st, lst):
	if st > lst:
		return None
	mid = (st + lst) // 2
	root = Node(A[mid])
	root.left = solve(A, st, mid - 1)
	root.right = solve(A, mid + 1, lst)
	return root

def deSerialize(A):
	st = 0
	lst = len(A) - 1
	return solve(A, st, lst)


def serialize(root, A):
	if not root:
		A.append('#')
		return A
	A.append(root.data)
	serialize(root.left, A)
	serialize(root.right, A)
	return A

def deSerialize(A):
	curr = A.pop(0)
	if curr == '#':
		return None
	result = Node(curr)
	result.left = deSerialize(A)
	result.right = deSerialize(A)
	return result


def serialize(root, A):
	q = [root]
	A.append(root)
	while len(q) > 0:
		temp = q[0]
		q.pop(0)
		if temp.left != None:
			A.append(temp.left)
			q.append(temp.left)
		else:
			A.append(None)
		if temp.right != None:
			A.append(temp.right)
			q.append(temp.right)
		else:
			A.append(None)

def deSerialize(A):
	root = A[0]
	q = [root]
	A = A[1:]
	for i in range(len(A) // 2):
		node = q[0]
		q.pop(0)
		node.left = A[2 * i]
		if A[2 * i] != None:
			q.append(A[2 * i])
		node.right = A[2 * i + 1]
		if A[2 * i + 1] != None:
			q.append(A[2 * i + 1])
	return root


from collections import deque

def serialize(root, A):
	if root == None:
		return ''
	q = deque([root])
	while q:
		node = q.popleft()
		if node:
			q.append(node.left)
			q.append(node.right)
		A.append(str(node.data) if node else '#')
	return A

def deSerialize(data):
	if not data:
		return None
	arr = data
	root = Node(int(arr[0]))
	q = deque([root])
	index = 1
	while q:
		node = q.popleft()
		if arr[index] != '#':
			node.left = Node(int(arr[index]))
			q.append(node.left)
		index += 1
		if arr[index] != '#':
			node.right = Node(int(arr[index]))
			q.append(node.right)
		index += 1
	return root


def serialize(root, A):
	if not root:
		A.append('#')
		return A
	A.append(root.data)
	serialize(root.left, A)
	serialize(root.right, A)
	return A

def deSerialize(A):
	tmp = A.pop(0)
	if tmp == '#':
		return None
	root = Node(tmp)
	root.left = deSerialize(A)
	root.right = deSerialize(A)
	return root


def serialize(root, A):
	if not root:
		return None
	arr = [root]
	while arr:
		t = arr.pop()
		if not t:
			A.append('#')
		else:
			A.append(str(t.data))
			arr.append(t.right)
			arr.append(t.left)

def deSerialize(A):
	if not A:
		return None
	global t
	t = 0
	return helper(A)

def helper(array):
	global t
	if array[t] == '#':
		return None
	root = Node(int(array[t]))
	t += 1
	root.left = helper(array)
	t += 1
	root.right = helper(array)
	return root


def serialize(root, A):
	if root == None:
		return
	serialize(root.left, A)
	A.append(root.data)
	serialize(root.right, A)

def deSerialize(A):

	def solve(A, l, h):
		if l > h:
			return None
		mid = (l + h) // 2
		root = Node(A[mid])
		root.left = solve(A, l, mid - 1)
		root.right = solve(A, mid + 1, h)
		return root
	l = 0
	h = len(A) - 1
	return solve(A, l, h)


def serialize(root, A):
	if not root:
		A.append('X')
		return
	A.append(str(root.data))
	serialize(root.left, A)
	serialize(root.right, A)
	return A

def deSerialize(A):
	if not A:
		return None
	val = A.pop(0)
	if val == 'X':
		return None
	node = Node(int(val))
	node.left = deSerialize(A)
	node.right = deSerialize(A)
	return node


def serialize(root, A):
	if root == None:
		A.append(-1)
		return
	A.append(root.data)
	serialize(root.left, A)
	serialize(root.right, A)

def deSerializeUtil(A):
	global index
	index += 1
	if A[index] == -1:
		return None
	root = Node(A[index])
	root.left = deSerializeUtil(A)
	root.right = deSerializeUtil(A)
	return root

def deSerialize(A):
	global index
	index = -1
	return deSerializeUtil(A)


def serialize(root, A):
	if root is None:
		return
	serialize(root.left, A)
	A.append(root.data)
	serialize(root.right, A)

def func(A):
	if not A:
		return None
	mid = len(A) // 2
	root = Node(A[mid])
	root.left = func(A[:mid])
	root.right = func(A[mid + 1:])
	return root

def deSerialize(A):
	return func(A)


def serialize(root, a):
	if root is None:
		return []
	q = []
	q.append(root)
	while q:
		cur = q.pop(0)
		if cur == None:
			a.append('#')
		else:
			a.append(cur.data)
		if cur:
			q.append(cur.left)
			q.append(cur.right)
	return a

def deSerialize(A):
	if len(A) == 0 or A[0] == '#':
		return None
	new_node = Node(A[0])
	q = []
	q.append(new_node)
	i = 1
	while q:
		cur = q.pop(0)
		if len(A) >= i:
			if A[i] == '#':
				cur.left = None
				i += 1
			else:
				lef_node = Node(A[i])
				cur.left = lef_node
				q.append(cur.left)
				i += 1
			if A[i] == '#':
				cur.right = None
				i += 1
			else:
				rigt_node = Node(A[i])
				cur.right = rigt_node
				q.append(cur.right)
				i += 1
	return new_node