# .css-df1pn7{display:block;width:16rem;}     # Day #3: Serializing and Deserializing a Binary Tree with Python.

Subscribe to my newsletter and never miss my upcoming articles

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 here to understand the recursion better, step by step.