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)