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);
}
}

### Like this:

Like Loading...

*Related*