Amazon Interview Question
SDE1sCountry: India
Interview Type: Phone Interview
Just sample, albiet not the cleanest implementation:
JSBin: jsbin.com/habamet/2/edit?js,console
function Node(val, left, right) {
this.val = val;
this.left = left;
this.right = right;
}
var root = new Node(
1,
new Node(2, new Node(3, null, new Node(4)) ),
new Node(5, new Node(6) )
);
function printTree(node) {
if (node) {
var left = printTree(node.left);
var mid = [node.val];
var right = printTree(node.right);
return mid.concat(left).concat(right);
}else return [];
}
function serializeTree(node) {
if (node) {
var s0 = node.val;
var left = serializeTree(node.left);
var right = serializeTree(node.right)
var s1 = left.length ? '(' + left + ')' : '';
var s2 = right.length ? '(' + right + ')' : '';
var s = s1.length || s2.length ? '(' + s0 + s1 + s2 + ')' : '' +s0;
return s;
}else {
return '';
}
}
function deserializeTree(serialized) {
if (!serialized.length) {
return null;
}else {
var token = parse(serialized);
//console.log(token);
var left = deserializeTree(token.left);
var right = deserializeTree(token.right);
var node = new Node(token.val, left, right);
return node;
}
}
function parse(serialized) {
function getToken(s, offset) {
if (!s.length || s[offset] !== '(') return '';
var count = 0;
var r = '';
for(var i = offset; i < serialized.length; ++i) {
var c = serialized[i];
if (c === '(') ++count;
else if (c === ')') --count;
r+= c;
if (count <= 0) break;
}
offset = i;
return r;
}
var offset = serialized.match(/\d/).index;
var val = serialized[offset];
var left = getToken(serialized, offset + 1);
var right = getToken(serialized, offset + 1 + left.length );
return {val: val, left: left, right: right};
}
var serialized = serializeTree(root);
console.log('serialized: ' + serialized );
var copyNode = deserializeTree( serialized );
console.log( 'deserialized: ' + printTree(copyNode) );
Output:
"serialized: (1((2((3(4)))))((5(6))))"
"deserialized: 1,2,3,4,5,6"
@agrawal so bossy :P
Just kidding anyways I was hoping the code was clear enough. The idea is to go to each node and serialize the node with its left subtree or right subtree. For example with the current tree
2
1 3
the serialize algo transverse each node and wraps its pharenthesis with its children, for example in the above tree when we are at node with value 2, we do
"(2 leftSubtree rightSubtree)
, where leftSubTree is serialized result of node with value 1 and rightSubtree is the serialized result of node with value 3, which at end will all result in
(2 (1)(3) )
To deserialize we simple parse the token into three parts [ nodeValue, leftSubtreeToken, rightSubtreeToken] then we deserialize leftSubtreeToken and rightSubtreeToken and use that result as left/right children for the current node. For example with the above serialized token parsing at first iterations would result in [2, "(1)", "(3)"]. Now current node value is 2, and we pass (1) to the same deserialize function and use that result as the left tree and similar for right tree.
Your best best is to step through code if you want to learn more or ask specific question.
Best.
void Serialize(Node const *n, vector<int> &out)
{
if (n == NULL) {
out.push_back(numeric_limits<int>::min());
return;
}
out.push_back(n->val_);
Serialize(n->left_, out);
Serialize(n->right_, out);
}
Node *Deserialize(vector<int> const &in, int &idx)
{
if (idx >= in.size() ||
in[idx] == numeric_limits<int>::min())
{
++idx;
return NULL;
}
Node *n = new Node(in[idx++]);
n->left_ = Deserialize(in, idx);
n->right_ = Deserialize(in, idx);
return n;
}
A pretty neat way is the recursive formulation as such:
Which produces :
From this, it is very easy to parse back into the tree.
The recursive formula of a any tree in this form is :
- NoOne August 23, 2017