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

https://gist.github.com/nmreddy1911/fd19ddcb1f3c3d9b0e97ae5ea8a508ac

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.

Please drop your queries in the comments section.

Thanks and cheers:)

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

Comments

100 Days Of Code

Day #4: Finding the smallest positive missing integer from an unordered list using Python.

More from this blog

DIY Portfolio: Unleashing Your Professional Story Online

Building Code Runner - Part #2 : Node.js Backend With Express Server and JDoodle API

Building Code Runner - Part #1 : Creating An Overview And MERN Project Setup With PNPM and Vite

Building Code Runner - Part #0

Day #8: Number Of Unival Trees Using Python

The Question On Day #3:

Algorithm

Python Visualiser To Understand The Recursion Better

Command Palette

Comments

100 Days Of Code

Day #4: Finding the smallest positive missing integer from an unordered list using Python.

More from this blog

The Question On Day #3:

Algorithm

Python Visualiser To Understand The Recursion Better