Design Gurus Logo
Serialize and Deserialize Binary Tree (hard)

Problem Statement

Serialization involves converting a binary tree into a string format such that it can be stored in the file or memory, preserving its structure and data.

Deserialization, on the other hand, is about reconstructing the binary tree from this string representation.

Design an algorithm to serialize and deserialize the binary tree. There is no restriction on designing the algorithm for serialization and deserialization of the binary tree.

Examples

Example 1:

  • Input: [1,2,3,null,null,4,5]
Image
  • Expected Output: [1,2,3,null,null,4,5]
  • Justification: The tree starts with the root node 1, followed by its left child 2 and right child 3. Since 2 and 3 have no left children, they are followed by null. Nodes 4 and 5 are the left and right children of 3.

Example 2:

  • Input: [5,4,null,3,null,2,null,1]
Image
  • Expected Output: [5,4,null,3,null,2,null,1]
  • Justification: This represents a skewed tree where each node except the last one has a left child. The serialized format follows the tree structure exactly.

Example 3:

  • Input: []
  • Expected Output: []
  • Justification: Since the tree is empty, both the serialized and deserialized outputs should be empty.

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

Unlock this and all other premium problems.
No code editor for this lesson
This lesson focuses on concepts and theory