(Balanced) BST serialization and deserialization

Binary Search tree is a unique sort of binary tree. Each node only contains elements that are smaller than its value in its left subtree and only elements that are larger than its value in its right subtree. Here is an example of a binary search tree:
30
20 40
10 35 45

To serialize the BST, we choose the pre-order traversal.
Why not post order or in order. Post order will have child come before the parents and it is not very simple to reconstruct tree. In order will have ambiguity when reconstruct the tree.

So we simply run a pre order traversal, we will have 30, 20, 10, 40, 35, 45. Then the serialization is done.

How do we de-serialize? we can re-build the tree using insertion. insert the node one by one, that will take nlgn time. Can we do better?

Remember the problem of validate BST

Notice that new nodes only append to the leaf nodes, and it came in the ascending order. So we pass the min and max value when building each leaf node. When a new node came, we check if it is in the range of the current leaf node, if so we append it and if not we go check the next range.


public class Test {
	int index;
	int [] data;
	public TreeNode deserializeBST(int [] input) {
		index = 0;
		data = input;
		return desBST(Integer.MIN_VALUE, Integer.MAX_VALUE); 
	}
	
	public TreeNode desBST(int min, int max) {
		TreeNode root = null;
		if (index == data.length) {
			return root;
		}
		else if (data[index] < max && data[index] > min) {// if the root value is between the 
			root = new TreeNode(data[index]);
			index++;
			root.left = desBST(min, root.val);
			root.right = desBST(root.val, max);
		}
		return root;
	}
	
	public static void main(String[] args) {
		Test t = new Test();
		int [] a1 = {30,20, 10, 40, 35, 45};
		TreeNode root = t.deserializeBST(a1);
	}
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s