1

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?

enter image description 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

1 Answer 1

2

In this line, when first number is entered in the tree, root will be None

for number in numbers:
    theTree.addNode(theTree.root, number)

Hence, line 20 is needed.

Sign up to request clarification or add additional context in comments.

8 Comments

why "when first number is entered in the tree, root will be None"?
Is it because of class Tree: def __init__(self): self.root = None ?
Yes when the tree is initialised, self.root = None
alright i see, but after that wouldn't the else part be neglected? Like in what situation, will the else part in line 21 be considered?
Also what does self.root = Node(value) in line 20 means here?
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.