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.

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

Web post with code visualization:
http://www.ideserve.co.in/learn/serialize-deserialize-binary-search-tree

Website: http://www.ideserve.co.in

Facebook: https://www.facebook.com/IDeserve.co.in