Serialize and Deserialize Binary Tree

Try to solve the Serialize and Deserialize Binary Tree problem.

We'll cover the following

Statement#

Serialize a given binary tree to a file and deserialize it back to a tree. Make sure that the original and the deserialized trees are identical.

  • Serialize: Write the tree to a file.

  • Deserialize: Read from a file and reconstruct the tree in memory.

Serialize the tree into a list of integers, and then, deserialize it back from the list to a tree. For simplicity’s sake, there’s no need to write the list to the files.

Constraints:

  • The number of nodes in the tree is in the range [0,500][0, 500].
  • −1000≤-1000 \leq Node.value ≤1000\leq 1000

Examples#

Created with Fabric.js 3.6.6 100 50 200 25 75 350 If you use Level Order Traversal If you use Preorder Traversal If you use Postorder Traversal 25 50 75 100 200 350 100 50 25 75 200 350 25 75 50 350 200 100 Example 1 50 25 75 200 350 100 50 25 75 200 350 100 If you use Inorder Traversal Input Output Binary Tree Binary Tree Integer List Serialization Deserialization Serialized List

1 of 2

Created with Fabric.js 3.6.6 If you use Level Order Traversal If you use Preorder Traversal If you use Postorder Traversal If you use Inorder Traversal Input Output Binary Tree Binary Tree Integer List 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 5 4 3 2 1 Example 2 Serialization Deserialization Serialized List

2 of 2

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Serialize and Deserialize Binary Tree

1

What is the serialized output of this tree using level order traversal?

          __ 350 
         |
      __ 75 ______ 
     |            |
     25 _     ___ 200 
         |   |
         50  100
A)

[350, 75, 25, 50, 200, 100]

B)

[350, 75, 25, 200, 50, 100]

C)

[25, 50, 75, 100, 200, 350]

D)

[50, 25, 100, 200, 75, 350]

Question 1 of 20 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to re-arrange them in the correct sequence

Perform a depth-first traversal and serialize individual nodes to the stream.

Also, serialize a marker to represent a NULL pointer that helps deserialize the tree.

Deserialize the tree using preorder traversal.

During deserialization, create a new node for every non-marker node using preorder traversal.

Try it yourself#

Implement your solution in serialize_deserialize.py in the following coding playground.

Python
usercode > serialize_deserialize.py
Input #1
%0 node_1 100 node_2 50 node_1->node_2 node_3 200 node_1->node_3 node_4 25 node_2->node_4 node_5 75 node_2->node_5 node_6 350 node_3->node_6
Visualization for Input #1
Serialize and Deserialize Binary Tree

Solution: Minimum Height Trees

Solution: Serialize and Deserialize Binary Tree