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