Java Program to Serialize and Deserialize a Binary Tree

This Java program demonstrates the serialization and deserialization of a binary tree. Serialization is the process of converting a tree into a string format which can be easily stored or transmitted, and deserialization reconstructs the tree from this string representation.

Binary Tree and Serialization Classes

The BinaryTree class includes methods to serialize the tree into a string and deserialize the string back into the tree structure using pre-order traversal.

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class BinaryTree {
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
            this.left = null;
            this.right = null;
        }
    }

    Node root;

    // Serialize the binary tree to a string
    public String serialize(Node root) {
        if (root == null) {
            return "null,";
        }
        String serialized = root.data + ",";
        serialized += serialize(root.left);
        serialized += serialize(root.right);
        return serialized;
    }

    // Deserialize the string back to the binary tree
    public Node deserialize(String data) {
        Queue<String> nodes = new LinkedList<>(Arrays.asList(data.split(",")));
        return deserializeHelper(nodes);
    }

    private Node deserializeHelper(Queue<String> nodes) {
        String val = nodes.poll();
        if (val.equals("null")) {
            return null;
        }
        Node node = new Node(Integer.parseInt(val));
        node.left = deserializeHelper(nodes);
        node.right = deserializeHelper(nodes);
        return node;
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);

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

        Node deserializedRoot = tree.deserialize(serialized);
        System.out.println("Tree deserialized successfully");
    }
}

Explanation of Serialization and Deserialization Methods

• serialize – This method uses a pre-order traversal to convert the tree into a comma-separated string of node values, using “null” for absent children to preserve the tree structure.
• deserialize – Converts the string back into a tree by recursively processing the node values from a queue which ensures that each node is recreated in the correct order.

Conclusion

The provided Java implementation effectively serializes a binary tree into a string and deserializes it back to the tree structure. This process is crucial for storing trees in databases, sending them over networks, or simply for persistent storage.