Serialize and Deserialize a Binary Tree

In this class, We discuss Serialize and Deserialize a Binary Tree.

Readers can prepare a full competitive coding course to crack product development companies. Click Here.

The reader should have basic coding skills to work with competitive coding. Click here.

Question:

Given a binary tree.

Our task is to serialize and deserialize a binary tree.

Serialize: To convert the binary tree to the array.

Deserialize: To convert the array to a binary tree.

The structure of the binary tree should be maintained.

Example:

The below diagram shows the serialization and deserialization of the binary tree.

Time complexity: O(N)

Space complexity: O(N)

We discussed the array representation of binary trees at heap data structure.

The space complexity required is O(2^h).

In this example, we need a space complexity of O(N).

Logic:

We use preorder traversal to serialize the binary tree.

We use the same preorder traversal to deserialize.

The step-by-step explanation is provided in the video.

Code:

class Node:

    # Constructor to create a new node

    def __init__(self, val):

        self.data = val

        self.left = None

        self.right = None

def serialize(root, A):

    #code here

    if root is None:

       A.append(-1)

       return

    A.append(root.data)

    serialize(root.left, A)

    serialize(root.right, A)

def deSerialize(A):

    #code here

    if len(A) == 0:

       return None

    val = A.pop(0)

    if val == -1:

       return None

    root = Node(val)

    root.left = deSerialize(A)

    root.right = deSerialize(A)

    return root

if __name__ == ‘__main__’:

    root = Node(1)

    root.left = Node(2)

    root.right = Node(3)

    root.left.left = Node(4)

    root.left.right = Node(5)

    root.right.left = Node(6)

    root.right.right = Node(7)

    root.right.left.right = Node(8)

    root.right.right.right = Node(9)

    print(“serialize and deserialize”)

    A=[]

    serialize(root,A)

    print(A)