Serialize and Deserialize
Get started
জয় শ্রী রাম
🕉Problem Statement:
Serialization is 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 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.
Example 1:
Input: root = [2,1,3]
Output: [2,1,3]
Example 2:
Input: root = []
Output: []
Solution:
I would highly encourage you to pay special attention to the implementation of deserialization as here we have implemented a very simple yet powerful approach using the most fundamental characteristic of a Binary Search Tree: for every node N1 all the nodes in the left subtree have values less than or equal to the value of node N1, and all the nodes in the right subtree have values greater than the value of node N1. It is for this characteristic that the INORDER Traversal of a Binary Search Tree happens to be always SORTED. This implementations could be reused in solving various other Binary Search Tree problems of all difficulty levels.
We already talked about Inorder Traversal for Binary Search Tree above. Now let's concentrate on the other two tree traversals,Preorder Traversal and Postorder Traversal, for a minute. In Preorder Traversal we
- visit a node.
- then traverse left subtree,
- at the end, we traverse right subtree.
n1
/ \
n2 n3
For the above node the Preorder Traversal would give n1 -> n2 -> n3
If you are well versed in Preorder Traversal and recursion, just by giving a little thoughts you would realize that if you are given the result of Preorder Traversal of a Binary Search Tree you could reconstruct the tree in the below way by leverage the basic characteristic of a Binary Search Tree:
public TreeNode reconstructBstFomPreorder(ArrayDeque<Integer> preorder) {
if (preorder.isEmpty()) {
return null;
}
return reconstructBST(preorder, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
public TreeNode reconstructBST(ArrayDeque<Integer> preorder, Integer lower, Integer upper) {
if (preorder.isEmpty()) {
return null;
}
int val = preorder.getFirst();
if (val < lower || val > upper) {
return null;
}
preorder.removeFirst();
TreeNode root = new TreeNode(val);
root.left = reconstructBST(preorder, lower, val);
root.right = reconstructBST(preorder, val, upper);
return root;
}
We already know that any Binary Tree could be reconstructed if you are given the result of inorder traversal and either preorder or postorder.
Inorder traversal of BST is an array sorted in the ascending order: inorder = sorted(preorder) OR sorted(postorder).
This means that BST structure is already encoded in the preorder or postorder traversal and we do not need to be given the result of the inorder traversal separately.
Using the discussion above we could say that Binary Search Tree could be constructed from preorder or postorder traversal only, as we just saw in the implementation above.
If we use Postorder instead of Preorder, the above implementation would look like below:
public TreeNode reconstructBstFomPostorder(ArrayDeque<Integer> postorder) {
if (postorder.isEmpty()) {
return null;
}
return reconstructBST(postorder, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
public TreeNode reconstructBST(ArrayDeque<Integer> postorder, Integer lower, Integer upper) {
if (postorder.isEmpty()) {
return null;
}
int val = postorder.getLast(); // we need to process from end for Postorder
if (val < lower || val > upper) {
return null;
}
postorder.removeLast(); // Remove the last element so that the second last element becomes available for processing
TreeNode root = new TreeNode(val);
root.right = reconstructBST(postorder, val, upper);
root.left = reconstructBST(postorder, lower, val);
return root;
}
From the above discussion the below two things are clear:
- Preorder or Postorder traversal result of a Binary Search Tree uniquely encodes a BST. So we could use either of Preorder or Postorder for serialization. The below implementation uses Preorder but you could use Postorder as well as shown above.
- We decode the encoded BST (either Preorder or Postorder) to get deserialized BST as shown above. The below code implements the same.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class BSTOperations {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) {
return "";
}
StringBuilder sb = preorder(root, new StringBuilder());
sb.deleteCharAt(sb.length() - 1); // delete last ' '
return sb.toString();
}
private StringBuilder preorder(TreeNode root, StringBuilder sb) {
if (root == null) {
return sb;
}
sb.append(root.val);
sb.append(' ');
preorder(root.left, sb);
preorder(root.right, sb);
return sb;
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data.isEmpty()) {
return null;
}
ArrayDeque<Integer> nums = new ArrayDeque<>();
for (String s : data.split("\\s+")) {
nums.add(Integer.valueOf(s));
}
return deserializeHelper(Integer.MIN_VALUE, Integer.MAX_VALUE, nums);
}
public TreeNode deserializeHelper(Integer lower, Integer upper, ArrayDeque<Integer> nums) {
if (nums.isEmpty()) {
return null;
}
int val = nums.getFirst();
if (val < lower || val > upper) {
return null;
}
nums.removeFirst();
TreeNode root = new TreeNode(val);
root.left = deserializeHelper(lower, val, nums);
root.right = deserializeHelper(val, upper, nums);
return root;
}
}
