Coding Interview Prep: BST Serialization in GoLang
How to Serialize and Deserialize a Binary Search Tree
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 valuesnodes := strings.Fields(data)
here we split the string into the node valuesnodeQueue := make([]int, len(nodes))
here we will store the nodesfor i, node := range nodes
for each value in nodes:val, _ := strconv.Atoi(node)
convert the string to an integer and save the valuenodeQueue[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
- again we're using recursion, this time to reconstruct our tree from the
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 exceptionsval := (*nodes)[0]
we pull the value from the front of thenodes
queueif 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 treenodes = (nodes)[1:]
redefine our queue but without the current node in itroot := &TreeNode{Val: val}
we create a node in the tree using the current valueroot.Left = this.deserializeHelper(nodes, min, val)
recursive call for values less than our current valueroot.Right = this.deserializeHelper(nodes, val, max)
recursive call for values greater than our current valuereturn 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 serializerdeser := Constructor()
instantiate our deserializertree := ser.serialize(root)
create our stringified treeans := 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.