## Facebook Interview Question for Software Engineers

• 1
of 1 vote

Country: United States
Interview Type: In-Person

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

Another simple Java solution similar to some of the C++ ones. We could avoid having 2 additional fields by extracting them into a value type that can be returned.

``````private static Node<Integer> head;

private static Node<Integer> tail;

private static void flattenRecursive(Node<Integer> n) {
if (n == null) {
return;
} else {
flattenRecursive(n.left);
} else {
tail.right = n;
n.left = tail;
tail = n;
}
flattenRecursive(n.right);
}
// Could make the list circular here
}``````

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

But here aren't you basically flattening the given Binary Tree into a Doubly Linked List?

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

This is the solution that I though in the interview.

So in order to make the tree a linked list you need to get the the last element from the list from the right and the first element from the list of the left.

Previously I've solved it returning a Tuple<Node,Node> with the first and last node of the "list".
But this is the right solution some variables could be removed but it is a mess not to have then for reference.

``````public static Node ConvertToList(Node root)
{
Node first = root;
Node last = root;

if(root == null)
return null;

Node previous = ConvertToList(root.Left);
Node next = ConvertToList(root.Right);

root.Left = root;
root.Right = root;

if(previous != null)
{
first = previous;
last = first.Left;

last.Right = root;
root.Left = last;
first .Left = root;
root.Right = first;

last = root;
}

if(next != null)
{
last = next.Left;
last.Right = first;
next.Left = root;
root.Right = next;
}

return first;
}``````

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

I ran into a similar question in the past. The difference is that the final list was not circular. Here is the code I wrote for that question. Again, this is not the full answer since the list is not circular, but a simple tweak would do the job.

``````def listfy(node):
if node is None:
return None, None

# Listfy the children first so the current node only needs to be
# inserted between the lists created from its children
if node._left:
if node._right:

if not l_tail and not r_head:
return node, node
else:
# if there is a list to the left, the current node becomes
# the new tail of that list and the head of the full list remains
# the same. Otherwise, the current node is the head of the
# current list.
if l_tail:
l_tail._right = node
node._left = l_tail
else:

# If there is a list to the right, the current node becomes
# the new head of that list and the tail of the full list remains
# the same. Otherwise, the current node is the tail of the
# the current list.
else:
r_tail = node

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

Something like the following:

We modify an inorder traversal to keep track of pointers to the "current" Node we are on in the list. We can also keep track of the head and tail of the list and after the inorder traversal, we simply link up the ends of the lists to make it circular.

I wrote this quickly, so there may be some syntax bug with the pointer logic (haven't done C pointers in a while) but I think it is the correct logic:

``````makeCircularList(Node treeHead) {

Node *tail;
Node *current;

}

modInorder(Node n, Node *current, Node * head, Node * tail) {

if (n == NULL) {

return;
}

Node previous;

}

tail = &n;

previous = modInorder(n.left, current);

current -> right = n;
current = &n;
current -> left = previous;

modInorder(n.right, current)

}``````

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

Not sure if it works as the signature of the function changed when you call it.

But I did had the same mistake as I forgot to make the current.Right.Left = current and current.Left.Right = current to make it a double linked list even though in the pseudo code I did.

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

``````#include "stdafx.h"
#include "stack"
#include "iostream"

using namespace std;
struct node {
node(int val, node* left, node* right):val(val),left(left),right(right){}
node(int val):val(val),left(NULL),right(NULL){}
node* left;
node* right;
int val;
};

node* prev_node = NULL;
node* first = NULL;

void build_double_list(node* root)
{
if(!root) {
return;
}
build_double_list(root->left);

if(!prev_node){
first = root;
}
else {
root->left = prev_node;
prev_node->right = root;

}
prev_node = root;

build_double_list(root->right);
}

node* convert_to_double_list(node* root)
{
build_double_list(root);
if(!first) {
return NULL;
}
first->left = prev_node;
prev_node->right = first;
return first;
}

int _tmain(int argc, _TCHAR* argv[])
{
//node n1(1),n2(2),n4(4),n7(7),n9(9),//leaf nodes
//	n3(3,&n2,&n4),n5(5,&n1,&n3),n8(8,&n7,&n9),n6(6,&n5,&n8);//n6 is root
//// output is 1 5 2 3 4 6 7 8 9

node n6(6);
node* circ_double_ptr = convert_to_double_list(&n6);

node* cur = circ_double_ptr;
do {
cout << cur->val << " ";
cur = cur->right;
_ASSERT(cur->left->right == cur);
_ASSERT(cur->right->left == cur);
}
while(cur != circ_double_ptr);

return 0;
}``````

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

``````Node * convert(Node * root)
{
if (root == NULL)
return root;

Node *left = convert(root->left);
if (left)
{
while (left->right)
{
left = left->right;
}
left->right = root;
root->left = left;
}

Node *right = convert(root->right);
if (right)
{
while (right->left)
{
right = right->left;
}
right->left = root;
root->right = right;
}

return root;
}

Node * treeToList(Node* root)
{
return NULL;

{
if (tail->right) tail = tail->right;
}

}``````

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

``````class Node
{
Node* left;
Node* right;
int val;
}

Node* f(Node* root)
{
if(!root) return nullptr;
}

{
if(root->left)
{
}
Node* right = root->right;
if(right)
{
}
}

{
{
return;
}
}``````

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

I've seen this question on here before. Here's the solution I have typed up from the previous time I saw it (IIRC this isn't the original way I solved it, but rather someone else's answer that had a better solution than mine):

``````void convertToCircularDLL(Node *root)
{
static Node *prev;

if (root == NULL)
{
return;
}
convertToCircularDLL(root->left);
if (prev == NULL)
{  // first node in list
}
else
{
prev->right = root;
root->left = prev;
}
prev = root;
convertToCircularDLL(root->right);
if (prev->right == NULL)
{ // last node in list
}
}``````

EDIT: Thinking about it again, this is wrong. It works...once. If you made tried to convert more than one tree, it wouldn't work because the prev and head pointers are static, so they would still contain data from the previous run. This can be fixed by making them Node** parameters to the function. The initial call can be made with the addresses of two Node pointers initialized to NULL.

``````Node *prev = NULL, *head = NULL;

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

``````TreeNode[] registr = new TreeNode;
convertBinaryTreeToCL(t1, registr);

public static void convertBinaryTreeToCL(TreeNode node, TreeNode[] register) {
if(node == null)
return ;

convertBinaryTreeToCL(node.left, register);

TreeNode prev = register;

}
else {
node.left = prev;
prev.right = node;

}
register = prev = node;

convertBinaryTreeToCL(node.right, register);

if(prev.right == null) {
}

}``````

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

``````#include <cstdlib>
#include <iostream>

using namespace std;

struct Node;
typedef pair<Node*, Node*> bounds;

struct Node {
Node *l, *r;
int data;

Node(int d) : data(d) { }

bounds flatten() {
bounds t, b(this, this);
if (l) {
t = l->flatten();
b.first = t.first;
t.second->r = this;
l = t.second;
}
if (r) {
t = r->flatten();
b.second = t.second;
t.first->l = this;
r = t.first;
}
return b;
}
};

int main() {

Node *root = new Node(1);
...
bounds b = root->flatten();

return 0;
}``````

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

This is equivalent to convert a BST to a doubly linked list. To make the Doubly linked list circular we can simply traverse the list (once created) to find the end.

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

To flatten the tree, in-order search is used and queue was used to store node in order.
Running time of this algorithm is O(n).

``````#include <list>
#include <iostream>
using namespace std;

struct node {
int value;
node * left;
node * right;
node(int v):value(v), left(0), right(0){}
};

void inorder_tree(node * r, list<node*>& queue)
{
if (!r)
return;
inorder_tree(r->left, queue);
queue.push_back(r);
cout << r->value <<" ";
inorder_tree(r->right, queue);
}

node * flatten_tree(node * root)
{
list<node*> queue;
inorder_tree(root, queue);
node* prev=0, * cur = 0, *start = 0;
list<node*>::iterator iter;
for(iter= queue.begin(); iter != queue.end(); iter++)
{
cur = (*iter);
if (prev == 0)
{
cur->left = cur;
start = cur;
}
else {
cur->left = prev;
prev->right = cur;
}
prev = cur;
}
prev->right = prev;
return start;
}``````

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

If no additional memory is allowed, the following algorithm can achieve the same running time of O(N).

``````#include <list>
#include <iostream>
using namespace std;

struct node {
int value;
node * left;
node * right;
node(int v):value(v), left(0), right(0){}
};

node* tail = 0;

void inorder_tree2(node* r)
{
if (!r)
return;
inorder_tree2(r->left);
{
} else {
tail->right = r;
tail = r;
}
inorder_tree2(r->right);
}

node * flat_tree(node *root)
{
inorder_tree2(root);
node * prev = 0;
while (cur != tail)
{
if (!prev)
{
cur->left = cur;
} else {
cur->left = prev;
}
prev = cur;
cur = cur->right;
}
//do something with tail
tail->left = prev;
tail->right = tail;
}``````

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

``````///

void BinaryTreeToLL(const Node *root, Node **newHead)
{
if (root == NULL || newHead == NULL) {
return;
}

if (root->left != NULL) {
BinaryTreeToLL(root->left);
}

Node *newNode = new Node();
newNode->data = root->data;

newNode->left = newNode->right = newNode;
} else {
end->right = newNode;
newNode->left = end;
}

if (root->right != NULL) {
BinaryTreeToLL(root->right);
}
}

\\\``````

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.