Serialize and Deserialize a binary tree in Java

Problem

For a binary tree class containing integer values, we want to write a pair of serialization and deserialization function. As a reminder, serialization is the process of taking an object and converting is into bytes, usually for either sending the data over the network or for storing it on disk. Many programming languages, like Java, offer some default serialization, but those are usually not human-readable.

Algorithm

For serialization, the easiest way is to go through the tree breadth-first and serializing the values as we go. The matching deserialization algorithm needs to reconstruct the tree from the result of the serialization algoritm. Since values are in breadth-first order, deserialization will follow a similar strategy as serialization, keeping a queue containing the nodes from the previous level in order to rebuild the current level.
In terms of data structures, using a StringBuilder for serialization is recommended, as it allows efficient append. For the breadth-first search part, we obviously need a queue.

Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71

// Encodes a tree to a single string. public String serialize(TreeNode root) { // We store the result in a StringBuilder for efficiency. StringBuilder result = new StringBuilder(); // Breadth-first search requires a queue. Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.add(root); while (queue.size() > 0) { // We pop the current node from the queue. TreeNode node = queue.remove(); // We need to add it to the serialization. if (node == null) { result.append("null"); } else { result.append(String.valueOf(node.val)); // Add the children to the queue. queue.add(node.left); queue.add(node.right); } // We use space as a separator. result.append(" "); // Note that we will have an extra space at the end. } return result.toString(); } // Decodes your encoded data to tree. public TreeNode deserialize(String data) { if (data.length() == 0) { return null; } // Our data is space-separated: we need to split it. String[] elements = data.split(" "); // We use a queue to reconstruct the tree in a // breadth-first search way. Queue<TreeNode> queue = new LinkedList<TreeNode>(); TreeNode root = StringToTreeNode(elements[0]); queue.add(root); // We iterate through the elements. Since we have an extra // space, we iterate only until elements.length - 1. int i = 1; while(i < elements.length - 1) { TreeNode local_root = queue.remove(); // If the element on the queue is null, then its children // could not have been serialized, we can skip to the next // node on the queue. if (local_root == null) { continue; } // local_root is not null, meaning that the serialization // appended the two children to the queue. Therefore we // know they are the next elements. TreeNode left = StringToTreeNode(elements[i]); local_root.left = left; queue.add(left); TreeNode right = StringToTreeNode(elements[i + 1]); local_root.right = right; queue.add(right); i = i + 2; } return root; } // An auxiliary function to convert from String to TreeNode. private TreeNode StringToTreeNode(String s) { if (s.equals("null")) { return null; } else { return new TreeNode(Integer.parseInt(s)); } }

This problem can be found on leetcode and career cup.