This page explains Java solution to problem Serialize and Deserialize Binary Tree
using Pre-Order Traversal
of binary tree data structure.
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 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.
Example 1:public String serialize(TreeNode root)
should be able to convert TreeNode to String.public TreeNode deserialize(String data)
should be able to convert String to back to TreeNode format.
package com.vc.hard;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class SerializeAndDeserializeBinaryTree {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
serialize(root, sb);
return sb.toString();
}
private void serialize(TreeNode root, StringBuilder sb) {
if(root == null) {
sb.append("NULL ");
}
else {
sb.append(root.val);
sb.append(" ");
serialize(root.left, sb);
serialize(root.right, sb);
}
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
Queue<String> q = new LinkedList<>(Arrays.asList(data.split(" ")));
return deserializeList(q);
}
private TreeNode deserializeList(Queue<String> q) {
if(q.isEmpty()) return null;
String element = q.peek();
if(element.equals("NULL")) {
q.poll();
return null;
}
else {
int value = Integer.parseInt(element);
q.poll();
TreeNode root = new TreeNode(value);
root.left = deserializeList(q);
root.right = deserializeList(q);
return root;
}
}
}
O(N) Where
N is total number of elements in an input tree.
O(N) Where
N is total number of elements in an input tree.