Binary Tree Serialization
Introduction
What is serialization?
"In the context of data storage, serialization is the process of translating data structures or object state into a format that can be stored (for example, in a file or memory buffer, or transmitted across a network connection link) and reconstructed later in the same or another computer environment."
For example, if we want to serialize an array (data structure) [1, 2, 3] we can just store as (string) [1, 2, 3].
If we want to serialize a linked list, 1 -> 2 -> 3, then we can store as 1 -> 2 -> 3.
If we want to serialize a hashmap, then we can store as {"key" : "value"}. (doesn't this remind you of json?)
Some applications in practice are XML, JSON, Protocol Buffers, etc.
Question (LC.297)
Design an algorithm to serialize and deserialize a binary tree.
Example
1
/ \
2 3
/ \
4 5
Serialized: [1, 2, 3, null, null, 4, 5]Analysis
How do we do this for a binary tree? We need to store the nodes in a certain order. What order should we pick We want the ones that the root is easy to identify. Aka preorder and level order (root will be stored first).
Approach 1: BFS (Level Order Traversal)
Serialize
Step 1 Construct Queue
Step 2 Convert the queue to string
func serialize(root)
Step 1 Construct Queue:
if (root == null) return ""
ArrayList<TreeNode> queue
TreeNode current
queue.enqueue(root)
// how to get at the right index?
// so this won't work and queue will never be empty
// No, No, No we want to store the entire tree from the beginning
--- ignore ---
while (!queue.isEmpty)
current = queue.get()
if (current == null) continue
queue.enqueue(current.left)
queue.enqueue(current.right)
end while
--- end ignore ---
// making the move
for i from 0 to queue.size() - 1
current = queue.get(i)
if (current == null) continue
queue.enqueue(current.left)
queue.enqueue(current.right)
end for
--- optional ---
// take out the leaves (nulls) at the lowest level to save space
while (queue.get(queue.size() - 1) == null)
queue.dequeue
end while
--- end optional ---
Step 2 Build String :
StringBuild result
result.append(queue.get(0).val);
for i from 1 to queue.size() - 1
if (queue.get(i) == null)
result.append("," + "null")
else
result.append("," + queue.get(0).val)
end for
return result.toString
end funcDeserialize
BFS on the encoded string
func deserialize(str)
if (str.equals("")) return null
String[] nodeValues = str.split(", ")
Queue<TreeNode> queue
index = 0
TreeNode root = new TreeNode(nodeValue[index++])
queue.enqueue(root)
while (index < nodeValues.length) // or !queue.isEmpty
current = queue.dequeue
if (nodeValues[index] == "null") {
leftChild = null
} else {
leftChild = new TreeNode(nodeValues[index])
queue.enqueue(leftChild)
}
index++
current.left = leftChild
if (nodeValues[index] == "null") {
rightChild = null
} else {
rightChild = new TreeNode(nodeValues[index])
queue.enqueu(rightChild)
}
index++
current.right = rightChild
end while
return root
end funcNotes: The goal of this approach is to make the thinking process as straightforward as possible. To be more elegant, we can store nulls[i] for all i to count the number nulls so far at each nodeValue. Then the left child will be values[2 * (i - nulls[i]) + 1] and the right child will be values[2 * (i - nulls[i]) + 2].
Approach 1 Code
public class Codec {
/**
* Encodes a tree to a single string
* Encoding format is (root, root.leftChild, root.rightChild,
* leftChild.leftChild, leftChild.rightChild, ...)
* @param root the root of a binary tree
* @return the serialization of the given binary tree
*/
public String serialize(TreeNode root) {
if (root == null) {
return "";
}
// Step 1 Construct Queue
// arraylist cause we want to store the entire tree
ArrayList<TreeNode> queue = new ArrayList<>();
TreeNode current;
queue.add(root);
for (int i = 0; i < queue.size(); i++) {
current = queue.get(i);
if (current != null) {
queue.add(current.left);
queue.add(current.right);
}
}
// Step 2 Build String
StringBuilder result = new StringBuilder();
result.append(queue.get(0).val);
for (int i = 1; i < queue.size(); i++) {
result.append(", ");
if (queue.get(i) == null) {
result.append("null");
} else {
result.append(queue.get(i).val);
}
}
return result.toString();
}
/**
* Decodes the encoded data to a binary tree
* @param data the serialzed binary tree (an encoded string)
* @return the root of the restored binary tree
*/
public TreeNode deserialize(String data) {
if (data.equals("")) {
return null;
}
String[] values = data.split(", ");
Queue<TreeNode> queue = new LinkedList<>();
int index = 0;
TreeNode root = new TreeNode(Integer.parseInt(values[index++]));
TreeNode current, leftChild, rightChild;
queue.offer(root);
while (index < values.length) { // or while (!queue.isEmpty())
current = queue.poll();
if (values[index].equals("null")) {
leftChild = null;
} else {
leftChild = new TreeNode(Integer.parseInt(values[index]));
queue.offer(leftChild);
}
index++;
current.left = leftChild;
if (values[index].equals("null")) {
rightChild = null;
} else {
rightChild = new TreeNode(Integer.parseInt(values[index]));
queue.offer(rightChild);
}
index++;
current.right = rightChild;
}
return root;
}
}Approach 2: DFS (Pre-order Traversal)
Serialize
Just a regular preorder traversal
Use a notebook (called result) to travel around the tree
func serialize(root)
StringBuilder result
preorder(root, result)
return result
end func
func preorder(root, result)
if (root == null)
result.append("N ")
result.append(root.val)
result.append(" ")
preorder(root.left, result)
preorder(root.right, result)
end funcDeserialize
We want to build this tree top down
Naturally, the recursive divide and conquer fits this role
func deserialize(encoded_data)
if (encoded_data == "null") return null
String[] values = encoded_data.split(" ")
return preorderDC(values)
end func
int index = 0
func preorderDC(values)
if (index >= values.length) return null
if (values[index] == "null") return null
TreeNode root = new TreeNode(values[index])
// we don't want to backtrack here
// we want a permanent change
// root.left = preorderDC(values, index + 1)
index++
root.left = preorderDC(values)
index++
root.right = preorderDC(values)
return root
end funcApproach 2 Code
public class Codec {
public String serialize(TreeNode root) {
StringBuilder result = new StringBuilder();
preorder(root, result);
return result.substring(0, result.length() - 1);
}
private void preorder(TreeNode root, StringBuilder result) {
if (root == null) {
result.append("null ");
} else {
result.append(root.val);
result.append(" ");
preorder(root.left, result);
preorder(root.right, result);
}
}
public TreeNode deserialize(String data) {
if (data.equals("null")) {
return null;
}
String[] values = data.split(" ");
return preorderDC(values);
}
private int index = 0;
private TreeNode preorderDC(String[] values) {
// base case
if (index >= values.length) {
return null;
}
if (values[index].equals("null")) {
return null;
}
// divide and conquer
TreeNode root = new TreeNode(Integer.parseInt(values[index]));
index++;
TreeNode leftSubtree = preorderDC(values);
index++;
TreeNode rightSubtree = preorderDC(values);
// merge
root.left = leftSubtree;
root.right = rightSubtree;
return root;
}
}Reference
Wikipedia Serialization
Last updated