Serialize and Deserialize Binary Tree in Java

Quick Links

Problem Description

Ah, the classic problem of Serialize and Deserialize Binary Tree! Imagine you have a tree, not the kind that gives you shade on a sunny day, but a binary tree filled with nodes. Your task, should you choose to accept it, is to convert this tree into a string (serialize) and then back into a tree (deserialize). It’s like turning a delicious cake into a recipe and then back into a cake again.

Why would you want to do this, you ask? Well, maybe you want to save your tree structure to a file or send it over the internet. But let’s be honest, who doesn’t want to play with trees in their spare time?

Code Solution


public class Codec {
  // Encodes a tree to a single string.
  public String serialize(TreeNode root) {
    if (root == null)
      return "";

    StringBuilder sb = new StringBuilder();
    Queue q = new LinkedList<>(Arrays.asList(root));

    while (!q.isEmpty()) {
      TreeNode node = q.poll();
      if (node == null) {
        sb.append("n ");
      } else {
        sb.append(node.val).append(" ");
        q.offer(node.left);
        q.offer(node.right);
      }
    }

    return sb.toString();
  }

  // Decodes your encoded data to tree.
  public TreeNode deserialize(String data) {
    if (data.equals(""))
      return null;

    final String[] vals = data.split(" ");
    TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
    Queue q = new LinkedList<>(Arrays.asList(root));

    for (int i = 1; i < vals.length; i += 2) {
      TreeNode node = q.poll();
      if (!vals[i].equals("n")) {
        node.left = new TreeNode(Integer.parseInt(vals[i]));
        q.offer(node.left);
      }
      if (!vals[i + 1].equals("n")) {
        node.right = new TreeNode(Integer.parseInt(vals[i + 1]));
        q.offer(node.right);
      }
    }

    return root;
  }
}

Approach Explanation

The code uses a breadth-first search (BFS) approach to serialize the binary tree. It traverses the tree level by level, appending the values of the nodes to a string. If a node is null, it appends "n" to represent that absence.

For deserialization, it splits the string back into values and reconstructs the tree using a queue to maintain the order of nodes. It’s like putting together a jigsaw puzzle, but with nodes instead of pieces!

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n), where n is the number of nodes in the tree.
Space Complexity	O(n) due to the storage of the serialized string and the queue used during the process.

Real-World Example

Think of a binary tree as a family tree. You want to keep track of your relatives (nodes) and their relationships (edges). When you serialize this family tree, you’re essentially writing down the family history in a book. Later, when you want to revisit your roots (pun intended), you can deserialize it back into a family tree.