Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns

Serialize and Deserialize Binary Tree

Understand how to serialize a binary tree into a list of integers and then deserialize it back to reconstruct the original tree. Explore the use of depth-first search techniques to handle tree serialization and deserialization, ensuring identical structure and values. This lesson helps you implement these operations efficiently for up to 500 nodes.

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

canvasAnimation-image
1 / 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]

1 / 2

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.

Sequence - Vertical
Drag and drop the cards to re-arrange them in the correct sequence
1
2
3
4

Try it yourself

Implement your solution in SerializeDeserialize.java in the following coding playground.

Java
usercode > SerializeDeserialize.java
// Definiton of a binary tree node class
// class TreeNode<T> {
//     T data;
//     TreeNode<T> left;
//     TreeNode<T> right;
//     TreeNode(T data) {
//         this.data = data;
//         this.left = null;
//         this.right = null;
//     }
// }
import java.util.*;
import ds_v1.BinaryTree.TreeNode;
public class SerializeDeserialize{
    public static List<String> serialize(TreeNode<Integer> root) {
        
        // Replace this placeholder return statement with your code
        return new ArrayList<>();
    }
    public static TreeNode<Integer> deserialize(List<String> stream){
        
        // Replace this placeholder return statement with your code
        return new TreeNode<Integer>(0);
    }
}
Serialize and Deserialize Binary Tree