## 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[0] 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] < 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[0] position for postorderArray lies within range min and max. If it does then we create a node and decrement currIndex[0] 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[0]. 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[0] 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.