Serializing and deserializing a binary tree in Java is one of the most popular code challenges to test your proficiency.
Serialization is the process of converting a data structure or object into a sequence of bits or a string.
The string that represents the object can then be stored in a text file or transmitted over a stream to other networks that requires that require the data.
Deserialization is the process of converting a sequence of bits back into its original object so it can be used by the programming language in its code.
The following graph illustrates the serialization and deserialization process of a binary tree:
The marker # in the graph above is used to represent the null value. It means that the node has no more child nodes.
This tutorial will help you learn how to serialize and deserialize a binary tree in Java.
But first, let’s create a TreeNode class that will be used to create a binary tree.
Creating the binary tree class in Java
The TreeNode class below is used to create a binary tree in Java:
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
You can then create the binary tree in the main() method as shown below:
TreeNode root = new TreeNode(9);
root.left = new TreeNode(3);
root.right = new TreeNode(5);
root.right.right = new TreeNode(6);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(7);
Now that you can create a binary tree, let’s learn how to serialize the binary tree object.
Serialize a binary tree in Java
First, create a new file for a Java class named BinaryTreeCodec or BTCodec for short.
Inside this class, create a new method named serialize() that returns a String and accepts a TreeNode object:
class BTCodec {
String serialize(TreeNode root) {
}
}
To serialize the TreeNode object, you need to call the serialize() method recursively, returning the root.val value as a string and concatenate them together.
When the root is null, you need to return the # symbol as the null marker:
String serialize(TreeNode root) {
if (root == null) {
return "#";
}
return "" + root.val + "," + serialize(root.left) + "," + serialize(root.right);
}
You can try out the serialize() method in the main() method of your Java project:
public class Main {
public static void main(String[] args) {
TreeNode root = new TreeNode(9);
root.left = new TreeNode(3);
root.right = new TreeNode(5);
root.right.right = new TreeNode(6);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(7);
BTCodec codec = new BTCodec();
String data = codec.serialize(root);
System.out.println(data);
}
}
The output of the data string above should be as follows:
9,3,1,#,#,7,#,#,5,#,6,#,#
The serialization process above will traverse the depth of the binary tree from the root.
Once you reach the end of the left-most nodes, the method will start traversing the right side of the child nodes. This is also known as the pre-order traversal method.
Now that you can serialize a binary tree in Java to a String, it’s time to learn how to deserialize it back into a binary tree.
Deserialize a binary tree in Java
Similar to the serialization process, you can deserialize a String back into a binary tree with the help of an ArrayList object.
Back in the BinaryTreeCodec class, you need to define a new method named deserialize() that returns a TreeNode and accepts a String as its argument:
TreeNode deserialize(String data) {}
First, you need to check if the data string is null. You can return a null value if it is.
When the data string is not null, then you can proceed to split the string into an ArrayList again.
After that, call a helper function named deserial() as shown below. You will define the method next:
TreeNode deserialize(String data) {
if (data == null){
return null;
}
List<String> values = new ArrayList<>(Arrays.asList(data.split(",")));
return deserial(values);
}
The deserial() method above will be a method that you can call recursively to build the binary tree from the given ArrayList.
Here’s the code for the deserial() method:
private TreeNode deserial(List<String> values){
String val = values.remove(0);
if (val.equals("#")) return null;
TreeNode root = new TreeNode(Integer.parseInt(val));
root.left = deserial(values);
root.right = deserial(values);
return root;
}
First, you use the remove() method to get the first element stored in the ArrayList.
When the value equals #, you can return null because it means the tree node doesn’t have any more value.
If the value is not null, then you create a new TreeNode object and use the Integer.parseInt() method to convert the String value into an int.
Then, you recursively call the deserial() method until all elements in the values list have been processed.
The method will return the root node of the TreeNode you’ve created.
Testing the code
Now that the BinaryTreeCodec class is complete, you can test the code as shown below:
public class Main {
public static void main(String[] args) {
TreeNode root = new TreeNode(9);
root.left = new TreeNode(3);
root.right = new TreeNode(5);
root.right.right = new TreeNode(6);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(7);
BTCodec codec = new BTCodec();
String data = codec.serialize(root);
System.out.println(data);
TreeNode deserialized = codec.deserialize(data);
System.out.println(deserialized.val);
System.out.println(deserialized.left.val);
System.out.println(deserialized.right.val);
System.out.println(deserialized.right.right.val);
System.out.println(deserialized.left.left.val);
System.out.println(deserialized.left.right.val);
}
}
The output of the above code will be as follows:
9,3,1,#,#,7,#,#,5,#,6,#,#
9
3
5
6
1
7
The TreeNode has been serialized and deserialized successfully using the BinaryTreeCodec class.
You can get all the code for this tutorial in the following GitHub repository:
Serialize and Deserialize binary tree using Java
You have learned how to serialize and deserialize a binary tree in this tutorial. Nice work! 😉