Coding Interview Prep: BST Serialization in GoLang

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 start by defining our Codec class and its constructor:

type Codec struct{}

func Constructor() Codec {
    return Codec{}
}

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

func (this *Codec) serialize(root *TreeNode) string {
    var sb strings.Builder
    this.serializeHelper(root, &sb)
    return sb.String()
}

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:

func (this *Codec) serializeHelper(node *TreeNode, sb *strings.Builder) {
    if node == nil {
        return
    }
    sb.WriteString(strconv.Itoa(node.Val) + " ")
    this.serializeHelper(node.Left, sb)
    this.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.

func (this *Codec) deserialize(data string) *TreeNode {
    if data == "" {
        return nil
    }
    nodes := strings.Fields(data)
    nodeQueue := make([]int, len(nodes))
    for i, node := range nodes {
        val, _ := strconv.Atoi(node)
        nodeQueue[i] = val
    }
    return this.deserializeHelper(&nodeQueue, -1<<31, 1<<31-1)
}

Going over this line by line:

if data == "" {return nil} this line takes care of errors from null values
nodes := strings.Fields(data) here we split the string into the node values
nodeQueue := make([]int, len(nodes)) here we will store the nodes
for i, node := range nodes for each value in nodes:
- val, _ := strconv.Atoi(node) convert the string to an integer and save the value
- nodeQueue[i] = val add it to the rest of the queue at index 'i'
return this.deserializeHelper(&nodeQueue, -1<<31, 1<<31-1); we use bitwise operators to define vary large negative and positive values
- again we're using recursion, this time to reconstruct our tree from the nodeQueue

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

func (this *Codec) deserializeHelper(nodes *[]int, min, max int) *TreeNode {
    if len(*nodes) == 0 {
        return nil
    }
    val := (*nodes)[0]
    if val < min || val > max {
        return nil
    }
    *nodes = (*nodes)[1:]
    root := &TreeNode{Val: val}
    root.Left = this.deserializeHelper(nodes, min, val)
    root.Right = this.deserializeHelper(nodes, val, max)
    return root
}

if len(*nodes) == 0 {return nil} error handling to take care of null pointer exceptions
val := (*nodes)[0] we pull the value from the front of the nodes queue
if val < min || val > max {return nil} 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 = (nodes)[1:] redefine our queue but without the current node in it
root := &TreeNode{Val: val} we create a node in the tree using the current value
root.Left = this.deserializeHelper(nodes, min, val) recursive call for values less than our current value
root.Right = this.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 :

ser := Constructor() to instantiate our serializer
deser := Constructor() instantiate our deserializer
tree := ser.serialize(root) create our stringified tree
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 GoLang

Comments