Reference: LeetCode
Difficulty: Medium

Problem

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure.

The encoded string should be as compact as possible.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

Analysis

Reference: Solution

To serialize a binary tree, we need to:

  • Encode tree structure.
  • Encode node values.
  • Choose delimiters to separate the values in the encoded string.

Preorder / Postorder Traversal

We can actually use the fact that BST could be constructed from preorder or postorder traversal only. It bases on the two facts:

  • Binary tree could be constructed from preorder / postorder and inorder traversal.
  • Inorder traversal of BST is an array sorted in the ascending order: inorder = sorted(preorder).

This means that BST structure (inorder) is already encoded in the preorder or postorder traversal.

Time: $O(N)$
Space: $O(N)$

Postorder

1
2
3
4
5
6
7
     6
/ \
3 9
/ \ \
1 5 10
/
4

Postorder: [ 1 4 5 3 10 9 6 ]

Read it from right to left, the rightmost value would be the root’s value of a subtree.

Serialize:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public String serialize(TreeNode root) {
if (root == null) {
return null;
}
StringBuilder sb = new StringBuilder();
postorder(root, sb);
sb.setLength(sb.length() - 1);
return sb.toString();
}

private void postorder(TreeNode root, StringBuilder sb) {
if (root == null) {
return;
}
postorder(root.left, sb);
postorder(root.right, sb);
sb.append(root.val + ",");
}

Deserialize:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public TreeNode deserialize(String data) {
if (data == null || data.length() == 0) {
return null;
}
String[] dataArray = data.split(",");
List<Integer> dataList = new LinkedList<>();
for (String s : dataArray) {
dataList.add(Integer.valueOf(s));
}
return helper(dataList, Integer.MIN_VALUE, Integer.MAX_VALUE);
}

private TreeNode helper(LinkedList<Integer> L, Integer lower, Integer upper) {
if (L.size() == 0) {
return null;
}
int val = L.getLast(); // root
if (val < lower || val > upper) { // check if this value is suitable in the place
return null;
}

L.removeLast();
TreeNode root = new TreeNode(val);
root.right = helper(L, val, upper);
root.left = helper(L, lower, val);

return root;
}

Preorder

1
2
3
4
5
6
7
     6
/ \
3 9
/ \ \
1 5 10
/
4

Postorder: [ 6 3 1 5 4 9 10 ]

Read it from left to right, the leftmost value would be the root’s value of a subtree.

Tiny Modification:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
private void preorder(TreeNode root, StringBuilder sb) {
if (root == null) {
return;
}
sb.append(root.val + ",");
preorder(root.left, sb);
preorder(root.right, sb);
}

private TreeNode helper(LinkedList<Integer> L, Integer lower, Integer upper) {
if (L.size() == 0) {
return null;
}
int val = L.getFirst(); // root
if (val < lower || val > upper) {
return null;
}

L.removeFirst(); // remove first
TreeNode root = new TreeNode(val);
root.left = helper(L, lower, val); // from left
root.right = helper(L, val, upper);

return root;
}

Other Optimizations

Approach 1: Convert int to 4-byte string to optimize space for node values.

Approach 2: Get rid of delimiters.

Since each integers could be represented as 4 bytes, we can treat the data as many chunks of 4 bytes.


Comment