## Facebook Interview Question for Software Engineers

Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
3
of 3 vote

I'm surprised, that this is a phone interview question.

1. Traverse the tree in Pre-Order form, push each node into a List.
2. For missing nodes, push null into the list.

``````public static List<Integer> getList(Tree root){
List<Integer> res = new ArrayList<>();
if(root == null) return res;
preOrder(root, res);
return res;
}

public static void preOrder(Tree root, List<Integer> res){
if(root == null){
return;
}
preOrder(root.left, res);
preOrder(root.right, res);
}``````

Then re-construct, the Tree back from the List.

``````public static Tree getTree(List<Integer> res){
Tree t = getTreeHelp(res);
return t;
}

private static Tree getTreeHelp(List<Integer> res){
if(res.size() == 0) return null;
Integer key = res.remove(0);
if(key == null) return null;
Tree root = new Tree(key);
root.left = getTreeHelp(res);
root.right = getTreeHelp(res);
return root;
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````public static List<Integer> store(Node root) {
storeTree(root, sol);
return sol;
}

private static void storeTree(Node root, List<Integer> sol) {
if(root == null) {
return;
}
storeTree(root.left, sol);
storeTree(root.right, sol);
}
// 5 3 1 null null null 2 6 null null 1 null null

public static Node restore(List<Integer> list) {
if (list.peek(0) == null)
return list.poll(0);

Node n = new Node(list.poll(0));
n.left = restore(list);
n.right = restore(list);
return n;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Traverse the tree in Level Order traversal
2. Create a new tree and just perform AddToTree operation on each item

``````public List<int> Store(Node ptr)
{
List<int> treeList = new List<int>();
LevelOrder(ptr, treeList);
return treeList;
}

private void LevelOrder(Node source, List<int> treeList)
{
HashSet<int> visited = new HashSet<int>();
Queue<Node> nextToVisit = new Queue<Node>();
nextToVisit.Enqueue(source);

while (nextToVisit.Count > 0)
{
Node ptr = nextToVisit.Dequeue();

if (ptr == null)
{
continue;
}

nextToVisit.Enqueue(ptr.left);
nextToVisit.Enqueue(ptr.right);
}
}

Node newRoot = null;
{
if (newRoot == null)
{
newRoot = CreateNewNode(val);
}
else
{
Node ptr = newRoot;
while (ptr != null)
{
if (val < ptr.val)
{
if (ptr.left != null)
{
ptr = ptr.left;
}
else
{
ptr.left = CreateNewNode(val);
break;
}
}
else
{
if (ptr.right != null)
{
ptr = ptr.right;
}
else
{
ptr.right = CreateNewNode(val);
break;
}
}
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void Store(Node const *n, vector<int> &list)
{
if (n == NULL) {
list.push_back(numeric_limits<int>::min());
return;
}
list.push_back(n->val_);
Store(n->left_, list);
Store(n->right_, list);
}

Node *Restore(vector<int> const &list, int &idx)
{
if (list[idx] == numeric_limits<int>::min()) {
++idx;
return NULL;
}
Node *n = new Node(list[idx++]);
n->left_ = Restore(list, idx);
n->right_ = Restore(list, idx);
return n;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static List<Integer> store(Node root) {
storeTree(root, sol);
return sol;
}

private static void storeTree(Node root, List<Integer> sol) {
if(root == null) {
return;
}
storeTree(root.left, sol);
storeTree(root.right, sol);
}
// 5 3 1 null null null 2 6 null null 1 null null

public static Node restore(List<Integer> list) {
if (list.peek(0) == null)
return list.poll(0);

Node n = new Node(list.poll(0));
n.left = restore(list);
n.right = restore(list);
return n;``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

I don't think the second part of the question is well defined. There are many trees that will have the same list representation. Consider the following trees

# 0
# \
# 0

and
# 0
# /
#0

my understanding is that both of these tress have to have a list representation of [0,0], so they are indistinguishable.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.