Given a binary tree, serialize is a process of converting it into sequence of bits (array) and deserialize is the process of converting it back to the original form using that bits.
Example
Input:
15
/ \
/ \
10 20
/ \
/ \
16 25
Output:
Serialzied:
[15, 10, null, null, 20, 16, null, null, 25, null, null]
or
[15, 10, 20, null, null, 16, 25]
Deserialized:
15
/ \
/ \
10 20
/ \
/ \
16 25
We are going to see the both iterative as well as recursive solution for serialize and deserialize the binary tree.
Serialize Binary Tree using DFS and BFS.
The idea is we are going to perform the level-order traversal on the binary tree which is a breadth first search for iterative solution and pre-order traversal which is depth first search for recursive and the store each value of the nodes in the array.
Iterative
- Use a queue to perform the BFS using level-order traversal on the binary tree.
- Add the first element in the queue initially and then start iterating the queue.
- In each iteration, get the first node from the queue add its value in the array and then push its left and right subtree back to the queue.
const serializeIterative = (root) => {
const res = [];
//create a queue
const queue = root ? [root] : [];
//Iterate the queue
while (queue.length) {
//Get the top node
let node = queue.shift();
//If node exists
if (node) {
//Push the node value
res.push(node.val);
//Add the left and right child
queue.push(node.left || null);
queue.push(node.right || null);
} else {
//Else push null
res.push(null);
}
}
//Remove the trailing nulls to optimize it further
while (res[res.length - 1] === null){
res.pop();
}
return res;
};
Input:
function Node(val) {
this.val = val;
this.left = null;
this.right = null;
}
const tree = new Node(1);
tree.left = new Node(2);
tree.right = new Node(3);
tree.right.left = new Node(4);
tree.right.right = new Node(5);
console.log(serializeIterative(tree));
Output:
[1, 2, 3, null, null, 4, 5]
Recursive
For recursive solution we will use the pre-order traversal and perform the DFS and store the values in an array. The traversal will be done by an inner function.
const serializeRecursive = (root) => {
// array
let res = [];
// recursive function to perform pre order traversal on Binary Tree
function traversal(node) {
// check for the first null value
if(node === null) {
res.push(null);
return;
}
res.push(node.val);
traversal(node.left);
traversal(node.right)
}
// start the Traversal
traversal(root);
return res;
};
Input:
function Node(val) {
this.val = val;
this.left = null;
this.right = null;
}
const tree = new Node(1);
tree.left = new Node(2);
tree.right = new Node(3);
tree.right.left = new Node(4);
tree.right.right = new Node(5);
console.log(serializeIterative(tree));
Output:
[1, 2, null, null, 3, 4, null, null, 5, null, null]
Time complexity for iterative and recursive solution is O(n) and space complexity is also O(n).
Deserialize Binary Search Tree.
Iterative
- Use a queue to form the tree again.
- Create the root node from the first element of the array and push it in the queue and start iterating the queue.
- In each iteration get the top node and assign the left and right child value to it by fetching the top values from the array, then push this left and right child back to the queue for further formation of subtrees.
const deserializeIterative = (arr) => {
//Base case
if (!arr.length){
return null;
}
//Create the root from first value
const root = new Node(arr.shift());
//Create the queue
const queue = [root];
//Iterate the queue
while (queue.length) {
let node = queue.shift(), val;
//Set the left and right child values
node.left = (val = arr.shift()) || val === 0 ? new Node(val) : null;
node.right = (val = arr.shift()) || val === 0 ? new Node(val) : null;
//Add the left and right child to the queue
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
//return the tree
return root;
};
Input:
console.log(deserializeIterative([15, 10, 20, null, null, 16, 25]));
Output:
15
/ \
/ \
10 20
/ \
/ \
16 25
Recursive
We use the same approach for deserializing recursively as we have done in iterative, all we have to do is call the same function for the right and left sub trees and assign its value. In each the function will pull the top value from the array and return it.
If there is no value in array then terminate the function.
const deserializeRecursive = (arr) => {
// recursive function
function reverseTraversal() {
// check for null or empty value
if(arr.length == 0) {
return ;
}
// Remove the root node or first element
const val = arr.shift();
// check for the null and return null
if(val == null) return null;
// Create a new Tree Node
let node = new Node(val);
// First check for left elements in tree
node.left = reverseTraversal();
// Second check for right elements in tree
node.right = reverseTraversal();
// Return the node
return node;
}
return reverseTraversal();
};
Input:
console.log(deserializeRecursive([15, 10, null, null, 20, 16, null, null, 25, null, null]));
Output:
15
/ \
/ \
10 20
/ \
/ \
16 25
Time complexity: O(n) for both solution.
Space complexity: O(n).