# Serialize and Deserialize a binary search tree using post order traversal

Given a binary search tree (BST), how can you serialize and deserialize it using post order traversal? 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 post-order traversal of this tree in an array. Serialized form then would be an array [1,4,3,2,6,8,7,5]. To construct the original binary tree from this array would be deserialization.

## Algorithm/Insights

For serialization, we can simply do a post-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 post-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 post-order traversal visits a given tree in L-R-N fashion(L:Left sub-tree, R:Right sub-tree, N:Node) and the tree that we are going to construct is a BST. We will try to understand this algorithm using post-order traversal array [1,2,4,3,6,8,9,7,5]. Because this is a post-order traversal array, last 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(1,2,4,3) and elements greater than 5 would be placed in the right sub-tree(6,8,9,7).Notice that sub-arrays [1,2,4,3] and [6,8,9,7] are also post-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 post-order traversal array[1,2,4,3], construct BST. And to create right sub-tree of root 5, we need to solve sub-problem: given post-order traversal array[6,8,9,7] 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(postorderArray = postorder, lowIndex = 0, highIndex = postorder.length-1).
2. If (low > high) return null; This is the base case for this algorithm.
3. Else
3a. Create a root with value postorder[high];
3b. Find the index of the last element in postorder array which is less than root value. Let's call this index divIndex. For example, for array [1,2,4,3,6,8,9,7,5], if root is 5 then last element less than 5 would be 3 and hence divIndex would be equal to index of element 3 which is also 3. All elements in the postorder array between the lowIndex (including lowIndex) and divIndex(including divIndex)  are going to be smaller than root node's value (lower half). Also all the elements in postorder array between indices (divIndex + 1) and (highIndex - 1) (including both extremes) are going to be greater than root node's value(greater half).
3b. Find the index of the last element in postorder array which is less than root value. Let's call this index divIndex. For example, for array [1,2,4,3,6,8,9,7,5], if root is 5 then last element less than 5 would be 3 and hence divIndex would be equal to index of element 3 which is also 3. All elements in the postorder array between the lowIndex (including lowIndex) and divIndex(including divIndex)  are going to be smaller than root node's value (lower half). Also all the elements in postorder array between indices (divIndex + 1) and (highIndex - 1) (including both extremes) are going to be greater than root node's value(greater 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(postorderArray = postorder, lowIndex = lowIndex, highIndex = divIndex).
Second recursive call - root.right = deserializeArray(postorderArray = postorder, lowIndex = divIndex + 1, highIndex = highIndex - 1).

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 post-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 post-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 update the index in post-order traversal array.

The algorithm steps are as following -
1. Initialize currIndex to postorderArray.length-1, min to Integer.MIN_VALUE and max to INTEGER.MAX_VALUE.
2. Call deserializeArrayOptimized(postorderArray = postorder, currIndex = currIndex, min =  min, max =  max)
3. If currIndex < 0 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 postorderArray lies within range min and max. If it does then we create a node and decrement currIndex value(remember postorder traversal visits tree in L-R-N fashion).
6. Since this is a post-order traversal(L-R-N), we first construct right sub-tree after constructing node and decrementing currIndex. To do this, we make a recursive call root.right = deserializeArrayOptimized(postorder, currIndex, root.val, max). 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.
7. Once the right sub-tree is constructed in the above step, currIndex would point to the element which would be in the left sub-tree of root. To complete the left sub-tree construction, we again make a recursive call root.left =  deserializeArrayOptimized(postorder, currIndex, min, root.val). Please note that, maximum value limit for all the nodes in the left sub-tree is adjusted to root.val which implies that no node in left sub-tree can have value greater 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 post-order traversal array, how can you construct original binary search tree out of it?
* @author Nilesh
*/

public class DeserializeBinarySearchTreePostorder {

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 printPostorder(TreeNode root)
{
if (root == null) return;

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

}

public TreeNode deserializeArrayOptimized(int[] postorder, int[] currIndex, int min, int max)
{
if (currIndex < 0) return null;

TreeNode root = null;

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

}

return root;
}

private int findDivision(int[] postorder, int value, int low, int high)
{
int i = high;
for (; i >= low; i--)
{
if (value > postorder[i])
break;
}
return i;
}

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

TreeNode root = new TreeNode(postorder[high]);

int divIndex = findDivision(postorder, root.val, low, high - 1);

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

return root;
}

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

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

DeserializeBinarySearchTreePostorder solution = new DeserializeBinarySearchTreePostorder();

int[] currIndex = new int;
currIndex = postorder.length - 1;

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

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

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

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

System.out.println("");

System.out.print("Postorder array for constructed BST is:");
solution.printPostorder(root);
}
}
```

## Order of the Algorithm

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