# Serialize and Deserialize a binary search tree

Given a binary search tree (BST), how can you serialize and deserialize it? Serialization is defined as storing a given tree in a file or an array. Deserialization is reverse of serialization where we need to construct the binary tree if we are given a file or an array which stores the binary tree.

For example, for the following BST,
5
2            7
1   3        6    8
4

Serialization could be that we store the pre-order traversal of this tree in an array. Serialized form then would be an array [5,2,1,3,4,7,6,8]. To construct the original binary tree from this array would be deserialization.

## Algorithm/Insights

For serialization, we can simply do a pre-order traversal of a given BST and store it in an array. The main problem we are going to solve is how to construct this BST given pre-order traversal array. To solve this problem, we will go through two algorithms here. First one, a more intuitive but takes more time than the second one.

Algorithm - 1:
Here the basic idea that we are going to use is that pre-order traversal visits a given tree in N-L-R fashion(N:Node, L:Left sub-tree, R:Right sub-tree) and the tree that we are going to construct is a BST. We will try to understand this algorithm using pre-order traversal array [5,2,1,3,4,7,6,8]. Because this is a pre-order traversal array, first element of this array that is 5 must be the root of the BST. Also, all the elements which are less than 5 would be placed in the left sub-tree(2,1,3,4) and elements greater than 5 would be placed in the right sub-tree(7,6,8).Notice that sub-arrays [2,1,3,4] and [7,6,8] are also pre-order traversals of left and right sub-trees respectively. Hence to create left sub-tree of root 5, we need to solve sub-problem: given pre-order traversal array[2,1,3,4], construct BST. And to create right sub-tree of root 5, we need to solve sub-problem: given pre-order traversal array[7,6,8] construct BST.

As you can see, given problem is now reduced to two sub-problems with same definition but with smaller array sizes. In short, this problem can be solved using recursion. The base case for this recursion would be that if the array size is 0, then we return an empty tree.

Putting these ideas in a formal algorithm -
1. Call deserializeArray(preorderArray = preorder, lowIndex = 0, highIndex = preorder.length-1).
2. If (low > high) return null; This is the base case for this algorithm.
3. Else
3a. Create a root with value preorder[low];
3b. Find the index of the first element in preorder array which is greater than root value. Let's call this index divIndex. All elements in the preorder array between the divIndex (including divIndex) and highIndex are going to be greater than root node's value (greater half). Also all the elements in preorder array between indices (lowIndex + 1) and (divIndex - 1) (including both extremes) are going to be smaller than root node's value(lower half).
3c. Using this divIndex, we make recursive calls to create left and right sub-trees out of lower half and greater half of array respectively.
First recursive call -  root.left  = deserializeArray(preorderArray = preorder, lowIndex = lowIndex + 1, highIndex = divIndex-1).
Second recursive call - root.right = deserializeArray(preorderArray = preorder, lowIndex = divIndex, highIndex = highIndex).

4. After step#3, left and right sub-trees for root are constructed and we return root to the calling function.

Worst case time complexity for this method is O(n^2). Worst case comes into play when the BST to be constructed is skewed. For example, above algorithm takes O(n^2) time to construct BST for pre-order traversal array [5,4,3,2,1].

Now let's look at the algorithm, which runs in O(n) time.
Algorithm 2 -
This algorithm makes use of binary search tree(BST) property that - values of all the nodes in the left sub-tree of a given node are less than given node's value and values of all the nodes in the right sub-tree of a given node  are greater than given node's value.

To construct a binary search tree out of given pre-order traversal array, we check if the element's value satisfies constraints for BST and if it does then we construct a node out of it and advance the index in pre-order traversal array.

The algorithm steps are as following -
1. Initialize currIndex to 0, min to Integer.MIN_VALUE and max to INTEGER.MAX_VALUE.
2. Call deserializeArrayOptimized(preorderArray = preorder, currIndex = currIndex, min =  min, max =  max)
3. If currIndex >= preorder.length return null. This condition if evaluated to true indicates that each element is now included in BST.
4. Initialize root to null.
5. Now check if value of element at currIndex position for preorderArray lies within range min and max. If it does then we create a node and increment currIndex value.
6. Since this is a pre-order traversal(N-L-R), we first construct left sub-tree using remaining pre-order array. To do this, we make a recursive call deserializeArrayOptimized(preorder, currIndex, min, root.val). Note that, maximum limit for all the nodes in left sub-tree is now adjusted to value of root node. This implies that no node in the left sub-tree can have value greater than or equal to root's value.
7. Once the left sub-tree is constructed in the above step, currIndex would point to the element which would be in the right sub-tree of root. To complete the right sub-tree construction, we make a recursive call deserializeArrayOptimized(preorder, currIndex, root.val, max). Please note that, minimum value limit for all the nodes in right sub-tree is adjusted to root.val which implies that no node in right sub-tree can have value less than or equal to root node's value.
8. After step#7, complete BST is constructed and we return the root to the calling function.

## Code Snippet

```
package com.ideserve.questions.nilesh;

/**
* <b>IDeserve <br>
* Given a binary search tree's pre-order traversal array, how can you construct original binary search tree out of it?
* @author Nilesh
*/

public class DeserializeBinarySearchTree {

class TreeNode
{
TreeNode left;
TreeNode right;
int val;

public TreeNode(int x)
{
this.val = x;
}
}

private void printInorder(TreeNode root)
{
if (root == null) return;

printInorder(root.left);
System.out.print(" "+ root.val + ",");
printInorder(root.right);
}

private void printPreorder(TreeNode root)
{
if (root == null) return;

System.out.print(" "+ root.val + ",");
printPreorder(root.left);
printPreorder(root.right);
}

private TreeNode deserializeArrayOptimized(int[] preorder, int[] currIndex, int min, int max)
{
if (currIndex >= preorder.length) return null;

TreeNode root = null;

if ((preorder[currIndex] > min) && (preorder[currIndex] < max))
{
root = new TreeNode(preorder[currIndex]);
currIndex += 1;
root.left = deserializeArrayOptimized(preorder, currIndex, min, root.val);
root.right = deserializeArrayOptimized(preorder, currIndex, root.val, max);
}

return root;
}

private int findDivision(int[] preorder, int value, int low, int high)
{
int i;
for (i = low; i <= high; i++)
{
if (value < preorder[i])
break;
}
return i;
}

private TreeNode deserializeArray(int[] preorder, int low, int high)
{
if (low > high) return null;

TreeNode root = new TreeNode(preorder[low]);

int divIndex = findDivision(preorder, root.val, low+1, high);

root.left = deserializeArray(preorder, low + 1, divIndex - 1);
root.right = deserializeArray(preorder, divIndex, high);

return root;
}

public static void main (String[] args)
{
/*
5
2            7
1   3        6    8
4
*/

int[] preorder = {5,2,1,3,4,7,6,8};

DeserializeBinarySearchTree solution = new DeserializeBinarySearchTree();

int[] currIndex = new int;
currIndex = 0;

int min  = Integer.MIN_VALUE;
int max  = Integer.MAX_VALUE;

TreeNode root = solution.deserializeArrayOptimized(preorder, currIndex, min, max);

// TreeNode root = solution.deserializeArray(preorder, 0, preorder.length - 1);

System.out.print("Inorder array for constructed BST is:");
solution.printInorder(root);

System.out.println("");

System.out.print("Preorder array for constructed BST is:");
solution.printPreorder(root);

}
}
```

## Order of the Algorithm

Time Complexity is O(n)
Space Complexity is O(1)