Problem:
Given a binary search tree. We want to serialize it to a string, later reconstruct the binary search tree from the string.
7
/ \
4 9
\ /
5 8
Solution:
We have 3 choice for serializing the bst, inorder, preorder and postorder.
In order won't be a good choice. 4 5 7 8 9 can be mapped back to many BSTs. We can chose 5 as root node, 4 as left subtree, 7 8 9 as right subtree, then we can reconstruct a different BST than the original one. Actually, we can choose any number in the sequence as root node and construct a different BST.
How about preorder presentation: 7 4 5 9 8
This string is interesting: the root node 7 is at first position. 7 divide the rest of the subarray into 2 halves. The first half 4 5 are all smaller than 7, the right half 9 8 are all bigger than 7.
Let's room in left half 4 5. Again, the root node 4 is at first position. The right branch element 5 is larger than 4. Since there is no elements smaller than 4, the left subtree is null.
Room in right half 9 8 has similar structure. The root is 9. The left branch is 8, no right branch since no value is bigger than 9.
How about postOrder presentation: 5 4 8 9 7
The root node 7 is at last position. 7 divide the rest of the subarray into 2 halves. The first half 5 4 is smaller, the right half 8 9 is larger.
Room in left half 5 4. The root node 4 is at last position. The right branch 5 is larger than 4, there is no element smaller than 4, so left branch is null.
Room in right half 8 9. The root node 9 is at last position. The left branch 8 is smaller than 9, there is no element larger than 9, so right branch is null.
Choose either preorder or postorder, we can serialize and deserialize the BST.
We need to traversal all the nodes, the cost is O(N).
During deserialize, we have to reconstruct N node tree, the space is O(N) as well.
class Solution {
public static void main(String...args) {
Node root = new Node(7,
new Node(4, null, new Node(5, null, null)),
new Node(9, new Node(8, null, null), null)
);
inOrder(root);
System.out.println();
StringBuilder sb = new StringBuilder();
searialize(root, sb);
String str = sb.toString();
System.out.println(str);
root = deserialize(str);
inOrder(root);
}
private static Node deserialize(String str) {
String[] a = str.split(",");
return arrayToTree(a, 0, a.length-1);
}
private static Node arrayToTree(String[] a, int start, int end) {
if(start > end || start < 0 || end > a.length - 1) return null;
int val = Integer.parseInt(a[start]);
Node root = new Node(val, null, null);
int i = 0;
for(i = start + 1; i <= end; i++) {
if(val < Integer.parseInt(a[i]))
break;
}
root.left = arrayToTree(a, start+1, i-1);
root.right = arrayToTree(a, i, end);
return root;
}
private static void searialize(Node root, StringBuilder sb) {
preOrder(root, sb);
}
private static void inOrder(Node root) {
if(root == null) return;
inOrder(root.left);
System.out.print(root.value + ",");
inOrder(root.right);
}
private static void preOrder(Node root, StringBuilder sb) {
if(root == null) return;
sb.append(root.value + ",");
preOrder(root.left, sb);
preOrder(root.right, sb);
}
private static class Node {
int value;
Node left;
Node right;
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
}
public static void main(String...args) {
Node root = new Node(7,
new Node(4, null, new Node(5, null, null)),
new Node(9, new Node(8, null, null), null)
);
inOrder(root);
System.out.println();
StringBuilder sb = new StringBuilder();
searialize(root, sb);
String str = sb.toString();
System.out.println(str);
root = deserialize(str);
inOrder(root);
}
private static Node deserialize(String str) {
String[] a = str.split(",");
return arrayToTree(a, 0, a.length-1);
}
private static Node arrayToTree(String[] a, int start, int end) {
if(start > end || start < 0 || end > a.length - 1) return null;
int val = Integer.parseInt(a[start]);
Node root = new Node(val, null, null);
int i = 0;
for(i = start + 1; i <= end; i++) {
if(val < Integer.parseInt(a[i]))
break;
}
root.left = arrayToTree(a, start+1, i-1);
root.right = arrayToTree(a, i, end);
return root;
}
private static void searialize(Node root, StringBuilder sb) {
preOrder(root, sb);
}
private static void inOrder(Node root) {
if(root == null) return;
inOrder(root.left);
System.out.print(root.value + ",");
inOrder(root.right);
}
private static void preOrder(Node root, StringBuilder sb) {
if(root == null) return;
sb.append(root.value + ",");
preOrder(root.left, sb);
preOrder(root.right, sb);
}
private static class Node {
int value;
Node left;
Node right;
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
}
Time complexity O(N), space complexity O(N).
