One Pager Cheat Sheet
- We can serialize and deserialize a binary tree by using
preorder traversal
to convert it to an integer array. - By using the preorder traversal algorithm, the root node, left sub-tree, and right sub-tree of a binary tree can be processed in that order.
- We can serialize a binary tree using preorder traversal, using a designated key
-1
to specify anull link
. - We can
deserialize
abinary tree
by recursively building it using preorder traversal. - The Java code for serialization (
treeToArray
) and deserialization (arrayToTree
) of a binary tree has a complexity of O(n) and a space complexity of O(n), as all keys and null links are stored.
This is our final solution.
To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.
xxxxxxxxxx
114
}
var assert = require('assert');
​
function serialize(root) {
let string = '';
​
function generateStr(node) {
if (!node) {
string += 'e ';
} else {
string += node.val + ' ';
generateStr(node.left);
generateStr(node.right);
}
}
​
generateStr(root);
​
return string;
}
​
function deserialize(data) {
let nodes = data.split(' ');
​
function generateTree() {
let val = nodes.shift();
​
if (val === 'e') {
return null;
} else {
let node = new Node(Number(val));
node.left = generateTree();
node.right = generateTree();
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
That's all we've got! Let's move on to the next tutorial.
If you had any problems with this tutorial, check out the main forum thread here.