Algorithms
Serialize and Deserialize Binary Tree
Design an algorithm to serialize and deserialize a binary tree.
There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.
For example, one possible format of serialized tree for the following binary tree could be – “1,2,3,null,null,4,5”
1
/ \
2 3
/ \
4 5
Recursive Serialize – comma separated values of nodes in pre order
We simply traverse the tree in preorder. We append root value with left subtree serialized string separated by comma and then append eft subtree serialized string. In order to handle leaves we use special token “null” to represent the null children of treenode leaves.
Recursive Deserialize
In order to reconstruct tree from the pre-order serialized string, we scan the string tokens from left to right. For each token, if it is not null then we create a root for this token value and recursively create left and right subtree by traversing in pre-order. Otherwise it is a null child of a leaf node. So, we return null. Important part of deserialization process is to scan the tokens across recursive calls. So, each time we create a root node from a token we need to update an iterator to point to next token.
public static String serialize(TreeNode root){
if(root == null){
return "null,";
}
StringBuilder ser = new StringBuilder();
ser.append(root.key);
ser.append(",");
ser.append(serialize(root.left));
ser.append(serialize(root.right));
return ser.toString();
}
public static TreeNode deserialize(String[] ser, int[] offset){
if(offset[0] >= ser.length || ser[offset[0]].trim().equals("null")){
offset[0]++;
return null;
}
TreeNode root = new TreeNode(Integer.parseInt(ser[offset[0]++]));
root.left = deserialize(ser, offset);
root.right = deserialize(ser, offset);
return root;
}
public static TreeNode deserialize(String ser){
String[] toks = ser.split(",");
return deserialize(toks, new int[]{0});
}
Iterative Serialize – comma separated values of nodes in BFS order
Simply traverse the tree in BFS order and enqueue all children. In case of leaves we push special node with MIN value. When we pop an item we can append the value of this node to string buffer unless this is a special node, in which case we append null to the buffer.
Iterative Deserialize
We can tokenize the serialized string by comma to get all the nodes value in the order of BFS traversal. We start from first token by creating root node out of it. Now, we can start another BFS traversal to rebuild the tree from root by scanning two elements each time to create two children of a node. So, each time we pop a node we scan next 2 tokens from serialized string to get 2 children of this node. We create left and right child nodes for the popped node unless they are “null”.
Below is an implementation of the above idea which runs in O(n) time and O(n) space. We can do this in O(1) space using O(1) space inorder traversal which is known as Morris Traversal. Please read my another post here on Morris Traversal.
public static class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if(root == null){
return "null";
}
StringBuffer serTree = new StringBuffer();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
TreeNode node;
while(!queue.isEmpty()){
node = queue.poll();
if(node.key == Integer.MIN_VALUE){
serTree.append("null,");
continue;
}
else{
serTree.append(node.key+",");
}
if(node.left != null){
queue.add(node.left);
}
else{
queue.add(new TreeNode(Integer.MIN_VALUE));
}
if(node.right != null){
queue.add(node.right);
}
else{
queue.add(new TreeNode(Integer.MIN_VALUE));
}
}
return serTree.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if(data == null || data.isEmpty() || data.startsWith("null")){
return null;
}
String[] nodes = data.split(",");
if(nodes.length == 0){
return null;
}
TreeNode root = new TreeNode(0);
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
TreeNode node;
int i = 0;
while(!queue.isEmpty()){
node = queue.poll();
node.key = Integer.parseInt(nodes[node.key]);
int left = i+1;
int right = i+2;
if(left < nodes.length-1 && !nodes[left].equals("null")){
TreeNode leftNode = new TreeNode(left);
node.left = leftNode;
queue.add(leftNode);
}
if(right < nodes.length-1 && !nodes[right].equals("null")){
TreeNode rightNode = new TreeNode(right);
node.right = rightNode;
queue.add(rightNode);
}
i+=2;
}
return root;
}
}
Exercise
Given the following two interface of serialized JSON string.
interface JSONTokenStream {
boolean hasNext();
JSONToken next();
boolean equals(JSONTokenStream s1, JSONTokenStream s2);
}
interface JSONToken {
int type(); // 0=StartObject, 1=EndObject, 2=Field
String name(); // null for EndObject
String value(); // null for StartObject, EndObject
}
Implement the equals method for JSONTokenStream interface so that we can compare if two streams are exactly same.
Exercise 2 : Serialize/Deserialize n-array Tree
Same as binary tree but need to put number of children in the serialized information and use it to deserialize.
static class SerializableTree{
public String value;
public ArrayList<SerializableTree> children = new ArrayList<test.SerializableTree>();
int childCount;
public SerializableTree(String val){
value = val;
}
public void addChild(SerializableTree child){
children.add(child);
}
public static String serializeRecursive(SerializableTree root){
StringBuilder serialized = new StringBuilder();
int childrenCount = root.children.size();
serialized.append(root.value);
serialized.append("#");
serialized.append(childrenCount);
serialized.append(",");
for(int i = 0; i<childrenCount; i++){
serialized.append(serializeRecursive(root.children.get(i)));
}
return serialized.toString();
}
private static SerializableTree deserializeRecursive(String[] ser, int[] offset){
String node = ser[offset[0]++];
String tok[] = node.split("#");
String val = tok[0];
int childCount = Integer.parseInt(tok[1].trim());
SerializableTree root = new SerializableTree(val);
for(int i = 0; i < childCount; i++){
root.addChild(deserializeRecursive(ser, offset));
}
return root;
}
public static SerializableTree deserializeRecursive(String ser){
return deserializeRecursive(ser.split(","), new int[]{0});
}
public static String serializeIterative(SerializableTree root){
StringBuilder serialized = new StringBuilder();
Queue<SerializableTree> queue = new LinkedList<SerializableTree>();
queue.offer(root);
while(!queue.isEmpty()){
SerializableTree node = queue.poll();
int childrenCount = node.children.size();
serialized.append(node.value);
serialized.append("#");
serialized.append(childrenCount);
serialized.append(",");
for(int i = 0; i<childrenCount; i++){
SerializableTree child = node.children.get(i);
queue.offer(child);
}
}
return serialized.toString();
}
public static SerializableTree deserializeIterative(String serialized){
Queue<SerializableTree> queue = new LinkedList<SerializableTree>();
String[] bfsNodes = serialized.split(",");
String rootSer[] = bfsNodes[0].trim().split("#");
SerializableTree root = new SerializableTree(rootSer[0].trim());
root.childCount = Integer.parseInt(rootSer[1].trim());
queue.offer(root);
int serIndex = 1;
while(!queue.isEmpty()){
SerializableTree node = queue.poll();
for(int i = 0; i< node.childCount; i++){
String childSer[] = bfsNodes[serIndex+i].trim().split(",");
SerializableTree child = new SerializableTree(childSer[0].trim());
child.childCount = Integer.parseInt(childSer[1].trim());
node.addChild(child);
queue.offer(child);
}
serIndex += node.childCount;
}
return root;
}
}