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

```go
type Codec struct{}

func Constructor() Codec {
	return Codec{}
}
```

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

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

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

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

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