Coding Interview Prep: BST Serialization in Java

Why Serialize a BST?

Serialization is converting a data structure into bits the purposes of storing the data in memory or as a file for later retrieval, or to use less space when transmitting it across a network connection.

A Binary Search Tree (BST) is usually serialized into a string, which is what we will do in this case.

Here's the entire code, the rest of the article will be spent explaining the logic behind each line:

Serialization

An effective method for serializing a BST is to perform a preorder traversal (root, left, right), storing the values in a string separated by spaces.

We first start by importing a few libraries that will help us:

import java.util.*;

We import java.util.LinkedList to store the nodes

Then we'll define a function to start encoding a tree into a single tree:

    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serializeHelper(root, sb);
        return sb.toString().trim();
    }

Here we use recursion to take care of the task, by passing in the root (or beginning) of our tree, and then defining a function serializeHelper which will:

store the value held in the node into the Stringbuilder
call itself on the left child of the node
call itself on the right child of the node

This eventually processes the entire tree.

With this in mind, serializeHelper should look like the following:

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

We add the line if (node == null) return; for when we get to the leaf nodes that have no children.

Deserialization

To deserialize, because we created the preorder traversal string, we can reconstruct the tree by repeatedly inserting the values into the BST.

    public TreeNode deserialize(String data) {
        if (data.isEmpty()) return null;
        Queue<Integer> nodes = new LinkedList<>();
        for (String s : data.split(" ")) {
            nodes.offer(Integer.parseInt(s));
        }
        return deserializeHelper(nodes, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

Going over this line by line:

if (data.isEmpty()) return null; this line takes care of errors from null values
Queue nodes = new LinkedList<>(); here we will store the nodes
for (String s : data.split(" ")) { nodes.offer(Integer.parseInt(s)); }
- Split the string between each space, and for each one:
  - convert it into an integer
  - add it to the end of the LinkedList
return deserializeHelper(nodes, Integer.MIN_VALUE, Integer.MAX_VALUE);
- again we're using recursion, this time to reconstruct our tree from the Queue nodes

Now we will define our deserializeHelper function, which handles the actual decoding of the BST from a queue into a BST data structure:

    private TreeNode deserializeHelper(Queue<Integer> nodes, int min, int max) {
        if (nodes.isEmpty()) return null;
        int val = nodes.peek();
        if (val < min || val > max) return null;
        nodes.poll();
        TreeNode root = new TreeNode(val);
        root.left = deserializeHelper(nodes, min, val);
        root.right = deserializeHelper(nodes, val, max);
        return root;
    }

if (nodes.isEmpty()) return null; error handling to take care of null pointer exceptions
int val = nodes.peek(); we pull the value from the front of the nodes queue
if (val < min || val > max) return null; we exit from the function if the nodes value is outside of the bounds we've defined before or if its not in the right place for our ordered tree
nodes.poll(); remove the current value from the queue
TreeNode root = new TreeNode(val); we create a node using the current value
root.left = deserializeHelper(nodes, min, val); recursive call for values less than our current value
root.right = deserializeHelper(nodes, val, max); recursive call for values greater than our current value
return root; We return our node after connecting it with its children, if any

Wrapping it up

And we're finished! With an in-order tree such as root=[2,1,3], we can serialize it with the following code :

Codec ser = new Codec(); to instantiate our serializer
Codec deser = new Codec(); instantiate our deserializer
String tree = ser.serialize(root); create our stringified tree
TreeNode ans = deser.deserialize(tree); decode it back into a BST

Thanks for following along, if you'd like to read more articles for coding interview questions then stay tuned as I plan to release a lot more in the coming days.

Coding Interview Prep: BST Serialization in Java

Comments