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:

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:

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

    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:

    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.

    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:

    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.

Coding Interview Prep: BST Serialization

Comments