Serialize and Deserialize a Binary Tree: Easy Explanation

Introduction

Serialize and Deserialize a Binary Tree is essential for tasks such as saving the tree’s state, sending it over a network, or storing it in a file. Serialization converts the tree into a string representation, while deserialization reconstructs the tree from this string.

Problem Statement

The goal is to implement two functions: one to serialize a binary tree into a string and another to deserialize the string back into the original tree structure. This is particularly useful when dealing with distributed systems or persistent storage.

Approach

A common way to serialize a tree is using a pre-order traversal (root, left, right). During serialization, we also need to record null children to preserve the tree’s structure. We’ll use a delimiter (like a comma) to separate node values and a placeholder (e.g., “null”) for missing nodes.

During deserialization, we’ll reverse the process. By reading values in pre-order, we rebuild the tree recursively.

Java Implementation

Below is a complete Java implementation using pre-order traversal.

//Unique class name for serialization and deserialization of binary trees
public class BinaryTreeCodec {

 // Converts a binary tree into a string representation
 public String encode(TreeNode root) {
     StringBuilder output = new StringBuilder();
     encodeTree(root, output);
     return output.toString();
 }

 private void encodeTree(TreeNode current, StringBuilder output) {
     if (current == null) {
         output.append("#,");
         return;
     }
     output.append(current.val).append(",");
     encodeTree(current.left, output);
     encodeTree(current.right, output);
 }

 // Restores a binary tree from its string representation
 public TreeNode decode(String data) {
     Queue<String> nodeValues = new LinkedList<>(Arrays.asList(data.split(",")));
     return decodeTree(nodeValues);
 }

 private TreeNode decodeTree(Queue<String> nodeValues) {
     if (nodeValues.isEmpty()) return null;

     String value = nodeValues.poll();
     if ("#".equals(value)) return null;

     TreeNode node = new TreeNode(Integer.parseInt(value));
     node.left = decodeTree(nodeValues);
     node.right = decodeTree(nodeValues);

     return node;
 }
}

//Tree node structure
class TreeNode {
 int val;
 TreeNode left;
 TreeNode right;

 TreeNode(int value) {
     this.val = value;
 }
}

Example Usage

Here’s how you can use the Codec class to serialize and deserialize a tree.

javaCopiaModificapublic class Main {
    public static void main(String[] args) {
        Codec codec = new Codec();

        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(5);

        String serialized = codec.serialize(root);
        System.out.println("Serialized: " + serialized);

        TreeNode deserialized = codec.deserialize(serialized);
        System.out.println("Deserialized Root: " + deserialized.val);
    }
}

Conclusion

Serialization and deserialization of binary trees are key for data storage and transmission. By using pre-order traversal and handling nulls carefully, you can faithfully convert a tree to a string and back without losing structure or data.

You can find the example code on Github.