Day #3: Serializing and Deserializing a Binary Tree with Python.
Tags: python, prolog, beginners
Published: 2020-06-13 09:23:32


  
  
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**  

{% gist https://gist.github.com/nmreddy1911/fd19ddcb1f3c3d9b0e97ae5ea8a508ac.js %}

**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](https://cscircles.cemc.uwaterloo.ca/visualize#code=class+Node%3A%0A++++def+__init__(self,+val,+left%3DNone,+right%3DNone)%3A%0A++++++++self.val+%3D+val%0A++++++++self.left+%3D+left%0A++++++++self.right+%3D+right%0A%0A%0Anode+%3D+Node('root',+Node('left',+Node('left.left')),+Node('right'))%0As+%3D+%22%22%0A%0A%23+serializing+function%0A%0A%0Adef+serialize(node,+s%3D%22%22)%3A%0A++++if(not+node)%3A%0A++++++++s+%2B%3D+%22%23+%22%0A++++++++return+s%0A++++s+%2B%3D+(str(node.val)%2B%22+%22)%0A++++s+%3D+serialize(node.left,+s%3Ds)%0A++++s+%3D+serialize(node.right,+s%3Ds)%0A++++return+s%0A%0A%0A%23+deserializing+function%0Ai+%3D+0%0A%0A%0Adef+deserialize(s)%3A%0A++++global+i%0A++++if+s%5Bi%5D+%3D%3D+%22%23%22%3A%0A++++++++if(i+%3C+len(s)-2)%3A%0A++++++++++++i+%2B%3D+2%0A++++++++return+None%0A++++else%3A%0A++++++++space+%3D+s%5Bi%3A%5D.find(%22+%22)%0A++++++++sp+%3D+space%2Bi%0A++++++++node+%3D+Node(s%5Bi%3Asp%5D)%0A++++++++i+%3D+sp%2B1%0A++++++++node.left+%3D+deserialize(s)%0A++++++++node.right+%3D+deserialize(s)%0A++++++++return+node%0A%0Aprint(%22String+after+serializing+node%3A+%22%2Bserialize(node))%0Aprint(%22Assert%3A%22,deserialize(serialize(node)).left.left.val+%3D%3D+'left.left')&mode=display&raw_input=&curInstr=223) to understand the recursion better, step by step.


Please drop your queries in the comments section.

**Thanks and cheers:)**