Facebook Interview Question
Software Engineer / DevelopersCountry: China
Interview Type: Phone Interview
Get idea from your (1), and implement it.
class Solution {
public static String treeToString(TreeNode root) {
StringBuilder ret = new StringBuilder("{");
if(root == null) ret.append("#");
else {
ret.append(root.val);
if(root.left != null || root.right != null) {
ret.append(treeToString(root.left));
ret.append(treeToString(root.right));
}
}
ret.append("}");
return ret.toString();
}
public static TreeNode stringToTree(String str) {
// get current tree
str = str.substring(1, str.length() - 1); // remove {}
if(str.charAt(0) == '#') return null;
int val = str.charAt(0) - '0';
str = str.substring(1); // remove root
TreeNode left = null, right = null;
int leftBraceCount = 0;
if(str.length() > 0) { // has childs
for(int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
if(ch == '{') leftBraceCount++;
if(ch == '}') leftBraceCount--;
if(leftBraceCount == 0) { // we find left and right child
left = stringToTree(str.substring(0, i + 1));
right = stringToTree(str.substring(i + 1));
break;
}
}
}
TreeNode root = new TreeNode(val, left, right);
return root;
}
public static void main(String[] args) {
TreeNode root = constructTree();
String str = treeToString(root);
root = stringToTree(str);
}
}
/** my implementation */
#include <iostream>
#include <string>
#include <deque>
struct BinTreeNode {
int val;
BinTreeNode *left, *right;
BinTreeNode() {}
BinTreeNode(int v, BinTreeNode *l = NULL, BinTreeNode *r = NULL):
val(v), left(l), right(r)
{}
};
void bin_tree_to_str(BinTreeNode *root, std::string& str)
{
if (root == NULL) return;
std::deque<BinTreeNode *> que;
BinTreeNode *p;
que.push_back(root);
str.append(std::to_string(root->val));
while (!que.empty()) {
//undef NDEBUG
//std::cout << "curr size: " << que.size() << std::endl;
p = que.front();
que.pop_front();
//undef NDEBUG
//std::cout << "size after pop_font: " << que.size() << std::endl;
//undef NDEBUG
//std::cout << p->val << std::endl;
//leaves
if (p->left == NULL && p->right == NULL) continue;
str.append("L");
if (p->left) {
que.push_back(p->left);
str.append(std::to_string(p->left->val));
} else {
str.append("#");
}
str.append("R");
if (p->right) {
que.push_back(p->right);
str.append(std::to_string(p->right->val));
} else {
str.append("#");
}
}
std::cout << str << std::endl;
}
BinTreeNode *str_to_bin_tree(const std::string& str)
{
std::deque<std::string> que;
size_t i, j, l;
for (i = 0, j = 0, l = str.size();
i < l;
/* void */) {
while (str[i] != 'L' && i < l) i++;
std::string ss = str.substr(j, i - j);
que.push_back(ss);
if (i == l) break;
j = i + 1;
i++;
while (str[i] != 'R' && i < l) i++;
ss = str.substr(j, i - j);
que.push_back(ss);
j = i + 1;
i++;
}
std::deque<BinTreeNode *> que2;
std::string str_val;
BinTreeNode *root, *left, *right;
BinTreeNode *temp;
str_val = que.front();
que.pop_front();
root = temp = new BinTreeNode(std::stoi(str_val));
que2.push_back(temp);
//while (!que2.empty()) {
while (!que.empty()) {
//for (i = 0, l = (que.size() - 1) / 2; i < l; i++) {
temp = que2.front();
que2.pop_front();
str_val = que.front();
que.pop_front();
if (str_val == "#") left = NULL;
else left = new BinTreeNode(std::stoi(str_val));
str_val = que.front();
que.pop_front();
if (str_val == "#") right = NULL;
else right = new BinTreeNode(std::stoi(str_val));
temp->left = left;
temp->right = right;
if (left) que2.push_back(left);
if (right) que2.push_back(right);
}
return root;
}
When serializing a binary tree, treat it as a complete binary tree (not a full binary tree), like adding NULL pointer to a single-child node (not really added).
When deserializing a string to a binary tree, first extract real contents (BinTreeNode.val) into a assistant double-ended queue, by removing L or R in between. And then constructing the binary tree, using another double-ended queue to maintain parents/children relationship.
Here's the tested code:
#include <vector>
#include <iostream>
#include <sstream>
#include <string>
#include <stdlib.h>
using namespace std;
struct Node {
long data;
Node* left;
Node* right;
Node(long d) : data(d), left(0), right(0) {}
};
void serialize (Node* root, stringstream& os)
{
if (!root) {
os << "$ ";
return;
}
os << root->data << " ";
serialize(root->left, os);
serialize(root->right, os);
}
Node* deserialize (stringstream& os)
{
string tok;
os >> tok;
if (tok == "$")
return 0;
Node* root = new Node(stoi(tok));
root->left = deserialize(os);
root->right = deserialize(os);
return root;
}
int main()
{
Node* root = new Node(4);
root->left = new Node(2);
root->left->right = new Node(3);
root->left->right->left = new Node(1);
root->right = new Node(5);
root->right->left = new Node(6);
root->right->right = new Node(7);
stringstream os;
serialize(root, os);
cout << os.str() << endl;
Node* dup = deserialize(os);
stringstream os2;
serialize(dup, os2);
cout << os2.str() << endl;
return 0;
}
void serialize(node *head, string &serial)
{
if(head == 0)
{
serial += "#,";
return;
}
serial += to_string(head->value)+",";
serialize(head->left,serial);
serialize(head->right,serial);
}
void deserialize(node * &head, string &serial, int &index)
{
int fou = serial.find(",",index);
string curr_val = serial.substr(index,fou - index);
index = index + curr_val.length() + 1;
if(curr_val == "#")
{
head = 0;
return;
}
else
{
head = new node;
//assuming values here are integers
head->value = atoi(curr_val.c_str());
deserialize(head->left,serial,index);
deserialize(head->right,serial,index);
}
}
You can use BFS to serialize the tree. Then, you simply need to insert the values in order to get the same exact tree. The order is:
"Root R L RR RL LR LL RRR RRL RLR RLL LRR LRL..."
I implemented a simple BST with "insert" only.
from Queue import *
class bst_node(object):
def __init__(self, p, l, r, v):
self.parent = p
self.right = r
self.left = l
self.value = v
class bst(object):
def __init__(self):
self.root = 0
def insert(self, value):
if self.root == 0:
self.root = bst_node(0, 0, 0, value)
else:
x = self.root
while True:
if x.value < value:
if x.right == 0:
x.right = bst_node(x, 0, 0, value)
break
else:
x = x.right
else:
if x.left == 0:
x.left = bst_node(x, 0, 0, value)
break
else:
x = x.left
def serialize(b):
q = Queue(maxsize = 0)
q.put(b.root)
s = ""
while not q.empty():
node = q.get()
if node.right != 0:
q.put(node.right)
if node.left != 0:
q.put(node.left)
# print this
if q.empty():
s = s + str(node.value)
else:
s = s + str(node.value) + " "
return s
def deserialize(string_bst):
values = string_bst.split(" ")
b = bst()
for k in range(0, len(values)):
value = int(values[k])
b.insert(value)
return b
numbers =[-5, 3, -2, 5, 10, 12, 11]
first_bst = bst()
for n in range(0, len(numbers)):
first_bst.insert(numbers[n])
str_first = serialize(first_bst)
print "First BST Serialized to:", str_first
second_bst = deserialize(str_first)
str_second = serialize(second_bst)
print "Second BST serialized to:", str_second
public static void serialize(Node root, OutputStreamWriter out){
if(root==null){
out.write(‘|’);
return;
}
out.write(root.data+””);
serialize(root.left);
serialize(root.right);
}
public static Node deserialize(InputStreamReader reader) throw IOException{
char c = (char)reader.read();
if(c==’|’){
return null;
}
Node n = new Node(c);
n.left=deserialize(reader);
n.right=deserialize(reader);
}
Should clarify with the interviewer what is the type of data the node holds.
Assuming the serialized data can fit into a char (it simplify, but don't impact the general principle): the most space efficient way I can think of is to use a string where the children of node at index n are placed at 2n+1 (left) and 2n+2 (right).
two different ways:
- samuel February 25, 20141) write with parentheis : root(left subtree string)(right subtree string)
2) write in-order sequence and (post-order or pre-order) sequence