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.