There is this problem asked by Google to design an algorithim to serialize and deserialize binary tree. I found one of the solutions online. The part i don't really understand is why the condition is necessary at line 20, where "if node == None:", self.root = Node(value) ? Because afterall this program will prompt the user to input nodes in the form eg: 1,3,5 in order for the program to work so therefore there won't be a case where node =none because user input is necessary? Am I misunderstanding something else here?
class Node:
def __init__(self, value):
self.left = None
self.right = None
self.value = value
class Tree:
def __init__(self):
self.root = None
def addNode(self, node, value): #Why when node==None, self.root= Node(value)?
if node == None:
self.root = Node(value)
else:
if value < node.value:
if not node.left:
node.left = Node(value)
else:
self.addNode(node.left, value)
else:
if not node.right:
node.right = Node(value)
else:
self.addNode(node.right, value)
def serialize(root):
values = []
def serializer(node):
if not node:
values.append('?')
else:
values.append(str(node.value))
serializer(node.left)
serializer(node.right)
serializer(root)
return ','.join(values)
def deserialize(s):
values = iter(s.split(','))
def deserializer():
val = next(values)
if val == '?':
return None
else:
node = Node(int(val))
node.left = deserializer()
node.right = deserializer()
return node
return deserializer()
if __name__ == '__main__':
# Read input, numbers separated by commas
numbers = [int(n) for n in input().split(',')]
theTree = Tree()
for number in numbers:
theTree.addNode(theTree.root, number)
s1 = serialize(theTree.root)
s2 = serialize(deserialize(s1))
print(s1)
print(s2)
assert s1 == s2
