# 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:

```java
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:

```java
    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:

```java
    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.

```java
    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:

```java
    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.