# Coding Interview Prep: BST Serialization

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

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1716856910557/047c7f46-6171-410d-9c3d-99ab0d232de2.png align="center")

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

```cpp
#include <string>
#include <sstream>
#include <queue>
```

* We import string because that is the structure that we will serialize and deserialize into.
    
* SStream (short for stringstream) associates a string object with a stream allowing us to read from the string as if it were a stream.
    
* Queue is the structure for organizing the BST in way that can be recreated later, and stores values in a FIFO (First in, First out) manner
    

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

```cpp
    string serialize(TreeNode* root) {
        stringstream ss;
        serializeHelper(root, ss);
        return ss.str();
    }
```

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

```cpp
    void serializeHelper(TreeNode* node, stringstream& ss) {
        if (!node) return;
        ss << node->val << " ";
        serializeHelper(node->left, ss);
        serializeHelper(node->right, ss);
    }
```

We add the line `if (!node) return;` for when we get to the leaf nodes and there are 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.

```cpp
    TreeNode* deserialize(string data) {
        if (data.empty()) return nullptr;
        stringstream ss(data);
        queue<int> nodes;
        string node;
        while (getline(ss, node, ' ')) {
            nodes.push(stoi(node));
        }
        return deserializeHelper(nodes, INT_MIN, INT_MAX);
    }
```

Going over this line by line:

* `if (data.empty()) return nullptr;` this line takes care of errors from null values
    
* `stringstream ss(data);` We construct a stringstream out of the encoded string
    
* `queue nodes;` Define the queue to hold the BST
    
* `string node;` Will hold the stringified node to be pushed into `nodes`
    
* `while (getline(ss, node, ' ')) { nodes.push(stoi(node)); }`
    
    * While there is input to read from `ss`,
        
        * store any characters until we get to a space
            
        * convert it from a string into an integer using `stoi`
            
        * push that integer into the `nodes` queue
            
* `return deserializeHelper(nodes, INT_MIN, INT_MAX);`
    
    * again we're using recursion, this time to reconstruct our tree from the `queue`
        

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

```cpp
    TreeNode* deserializeHelper(queue<int>& nodes, int min, int max) {
        if (nodes.empty()) return nullptr;
        int val = nodes.front();
        if (val < min || val > max) return nullptr;
        nodes.pop();
        TreeNode* root = new TreeNode(val);
        root->left = deserializeHelper(nodes, min, val);
        root->right = deserializeHelper(nodes, val, max);
        return root;
    }
```

* `if (nodes.empty()) return nullptr;` error handling to take care of null pointer exceptions
    
* `int val = nodes.front();` we pull the value from the front of the `nodes` queue
    
* `if (val < min || val > max) return nullptr;` 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.pop();` 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.