Introduction

When working with binary trees, you might encounter situations where you need to store the tree structure or transmit it over a network. This is where serialization and deserialization come into play. Serialization is the process of converting a data structure into a format that can be easily stored or transmitted, while deserialization is the reverse process of reconstructing the data structure from the serialized format.

In this blog post, we'll explore how to serialize and deserialize binary trees in Java, providing you with a solid understanding of these important operations.

Binary Tree Structure

Before we dive into serialization and deserialization, let's quickly review the structure of a binary tree in Java:

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

Serialization

Serialization involves converting the binary tree into a string representation. We'll use a pre-order traversal approach and denote null nodes with a special character (e.g., "#"). Here's how we can implement the serialization process:

public class Codec {
    private static final String DELIMITER = ",";
    private static final String NULL_MARKER = "#";

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) {
            return "";
        }
        StringBuilder sb = new StringBuilder();
        serializeHelper(root, sb);
        return sb.toString();
    }

    private void serializeHelper(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append(NULL_MARKER).append(DELIMITER);
            return;
        }
        sb.append(node.val).append(DELIMITER);
        serializeHelper(node.left, sb);
        serializeHelper(node.right, sb);
    }
}

In this implementation, we use a StringBuilder to efficiently build our serialized string. We perform a pre-order traversal of the tree, appending each node's value (or "#" for null nodes) to the string, separated by commas.

Deserialization

Deserialization is the process of reconstructing the binary tree from its serialized string representation. We'll use a queue to keep track of the nodes as we rebuild the tree:

public class Codec {
    // ... (previous code for serialization)

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data.isEmpty()) {
            return null;
        }
        Queue<String> queue = new LinkedList<>(Arrays.asList(data.split(DELIMITER)));
        return deserializeHelper(queue);
    }

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

In this deserialization process, we first split the input string into a queue of values. Then, we recursively build the tree, creating nodes for non-null values and returning null for the NULL_MARKER.

Example Usage

Let's see how we can use these methods with an example:

public class Main {
    public static void main(String[] args) {
        // Create a sample binary tree
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.right.right = new TreeNode(5);

        Codec codec = new Codec();

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

        // Deserialize the string back to a tree
        TreeNode deserialized = codec.deserialize(serialized);

        // Verify by serializing the deserialized tree
        String reserialized = codec.serialize(deserialized);
        System.out.println("Reserialized tree: " + reserialized);

        // Check if the original and reserialized strings match
        System.out.println("Match: " + serialized.equals(reserialized));
    }
}

Output:

Serialized tree: 1,2,4,#,#,#,3,#,5,#,#,
Reserialized tree: 1,2,4,#,#,#,3,#,5,#,#,
Match: true

Time and Space Complexity

Both serialization and deserialization have a time complexity of O(n), where n is the number of nodes in the tree, as we visit each node once.

The space complexity for serialization is O(n) to store the serialized string. For deserialization, the space complexity is O(n) for the queue and the call stack during recursion.

Conclusion

Serialization and deserialization of binary trees are essential operations when working with tree structures in various applications. By understanding and implementing these techniques, you'll be better equipped to handle binary trees in scenarios involving data storage, transmission, or interoperability between different systems.