Day #3: Serializing and Deserializing a Binary Tree with Python.

Hello, today is the Day 3 of the #100DaysOfCodeChallenge. Received a problem previously asked by Google with a medium tag to it. This is also listed in the hard set of problems on LeetCode.

The Question On Day #3:

Given the root to a binary tree, implement serialize(root), which serializes the tree into a string, and deserialize(s), which deserializes the string back into the tree.
For example, given the following Node class

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

The following test should pass:

node = Node('root', Node('left', Node('left.left')), Node('right'))
assert deserialize(serialize(node)).left.left.val == 'left.left'

Algorithm

• Create the binary tree using the Node class.
• Serializing:
  • To serialize the tree into a string, I considered the null nodes as #.
  • Starting from root, Depth First Search is used to traverse through the tree.
  • If a node exists, its value is appended to the string and the left sub tree is traversed.
  • This process continues until there are no more children left. Then a '#' is appended to the array and the recursive function is exited.
  • Then the right sub tree is traversed and the same process is followed.
  • The final resulting is string is returned.
• Deserializing:
  • To deserialize a string to form a tree, the first word in the space seperated string is considered as the root.
  • When a '#' is encountered, it is considered as a empty node and None is returned.
  • In the remaining cases, a new node with the value as the word is formed and the remaining string is traversed.
  • This function is called recursively until the end of the string is reached.

Python Code

Output

String after serializing node: root left left.left # # # right # # 

Assert: True

Python Visualiser To Understand The Recursion Better

View the visualisation of the above code in the Python Visualiser to understand the recursion better, step by step.

Please drop your queries in the comments section.

Thanks and cheers:)