## Facebook Interview Question for Software Engineer Interns

Country: United States
Interview Type: Phone Interview

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

just a variant question of converting it into singly linked list

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

Are you considering it as a BST? Also result should be sorted linked list.

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

``````class node{
public:
int key;
node* left;
node* right;
node(int key) {
this->key = key;
left = right = 0;
}
};

node *degenerate(node *root) {
if (!root) return 0;
node *newroot = 0;
for(newroot = root;newroot->left;newroot = newroot->left);
convertToList(root);
return newroot;
}

void convertToList(node *p) {
node *leftHighest = 0;
if (p->left) {
for(leftHighest = p->left;leftHighest->right;leftHighest = leftHighest->right);
convertToList(p->left);
leftHighest->right = p;
leftHighest->left = 0;
}

node *rightLowest = 0;
if (p->right) {
for(rightLowest = p->right;rightLowest->left;rightLowest = rightLowest->left);
convertToList(p->right);
p->right = rightLowest;
p->left = 0;
}
}``````

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

Can you explain me your approach ?

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

I apologise for the delay in replying. The method convertToList(node *p) is basically a slight variant of the recursive inorder algorithm.
This converts a binary tree with root p into a linked list where nodes are ordered in inorder fashion. (Hence the first node will be the extreme left of the tree).
The leftHighest node is basically the largest node of p->left subtree if it were a BST (the rightmost node of p->left).
Once I convert subtree p->left to linkedlist (by recursion), I add p to the end of the list (using 'right' pointer).
Next, I convert p->right subtree to linkedlist (by recursion) and attach it to the end of the above tree. The first node of the former will be the lowest node of p->right (rightLowest) if it were a BST, which is the leftmost node of p->right.

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

``````bT *head = NULL;
bT *tail = NULL;
bT *tmp = NULL;

{

{
s->left = s;
return;
}

//if node data greater than tail then insert at last pos
else if (s->data > tail->data)
{
s->left = tail;
tail->right = s;
tail = s;
}

//if node data less than head then insert at fisrt pos
{
s->left = s;
}

else  // else insert in between
{
while(tmp !=NULL)
{
if(tmp->data > s->data)
{
s->right = tmp;
s->left = tmp->left;
tmp->left->right = s;
tmp->left = s;
break;
} // if
tmp = tmp->right;
} // while

}//else

void treeToList(bT *s)
{
if(NULL == s)     return;

treeToList(s->left);
treeToList(s->right);
}``````

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

Let me know if it works...
Thanks.

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

And you may traverse via the head->right and so on.

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

recursive, degenerate left subtree,hook current root to it, root.'s right node is degenerated right subtree

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

the given tree is a BST,right?

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

the given tree is a BST,right?

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

No, it isnt

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

``````public Node convertToLinkList() {
}
}

Node last = null;

if (root == null) {
return;
}

root.mLeft = last;
if (last != null) {
last.mRight = root;
}
last = root;
}``````

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

Why can't one just do an inorder_treewalk and convert into singly linked list?
- Add each TreeNode to head of the ListNode if descending sorted list is required, otherwise add to a Tail ListNode...

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

Because its not a BST.

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

``````public Node degenerateTree(Node root){
if(root!=null){
Node newRoot = degenerateTree(root.left);
Node node = degenerateTree(root.right);
root.left = null;
if(node!= null){
root.right = node;
}
if(newRoot != null){
Node focusNode = newRoot;
while(true){
if(focusNode.right == null){
focusNode.right = root;
return newRoot;
}
focusNode = focusNode.right;
}
}
}
return root;
}``````

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

The below code creates and in order single linked list. You need to sort it.
The node "head" points to the start of the single linked list.
I initially create the double linked list and then remove the left links.

``````Node head = null;
boolean firstTime = true;

// TODO Auto-generated method stub

if( root == null) {
return null;
}

if(root.left != null){

while(leftTreeNode.right != null){
leftTreeNode = leftTreeNode.right;
}

leftTreeNode.right = (root);
}

if(firstTime && root.left == null) {
firstTime = false;
}

if(root.right != null){

while(rightTreeNode.left != null){
rightTreeNode = rightTreeNode.left;
}

root.right = (rightTreeNode);
}

return root;
}

while(temp != null) {
temp.left = null;
temp = temp.right;
}
}``````

This worked. i have tested it. If you find any issues in the code please let me know. I am yet to sort it though.

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

Didn't work for a standard 7 node perfectly balanced tree

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

Algo
Remove min element from Btree and place it to the right of right most element;

Remove 2nd min element from BTree and place it to the right of right most element.

............ continue upto nth min element;

Complexity
O(n ^2) To remove min element in each iteration will take O(n).

code
This algo can be coded using recursion with some temp variables.

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

I think this question is just to transfer a given unbalanced BST to a double linked list.

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

``````/**
* Convert a tree to a linked list with left pointing to NULL, i.e use right for next pointer.
* Does it in place.
*/
node_t *merge_lists(node_t *ll, node_t *root, node_t *lr)
{
// get the rightOf(ll)
node_t *llr = NULL;

if (ll && ll->right)
llr = ll->right;
else if (ll) llr = ll;

for (; llr && llr->right; llr = llr->right);

// point rightOf(ll) to root
if (llr) {
llr->right = root;
}

// mark root's left as NULL
root -> left = NULL;

// points root's right to lr
root -> right = lr;

// return ll, the new list head.
if (ll) return ll;

// if left is NULL then our list head is root.
return(root);
}

node_t * degen_tree(node_t *root)
{
if (!root)
return NULL; // base case.

node_t *left_l = degen_tree(root->left);
node_t *right_l = degen_tree(root->right);

node_t *head = merge_lists(left_l, root, right_l);
}``````

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

DFS for tree, if node doesn't have children remove node from parent and node become root of tree.

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

``````class TreeNode
{
int data;
TreeNode left=null,right=null;
TreeNode(int data)
{
this.data=data;
}
TreeNode rightMost()
{
TreeNode tra=this;
while(tra.right!=null)
tra=tra.right;
return tra;
}
}
class BTtoDTSorted
{
{
{
return;
}
{
}
else if(tail.data<node.data)
{
tail.right=node;
tail=node;
}
else
{
while(tra.right!=null)
{
if(tra.right.data>node.data)
{
TreeNode temp=tra.right;
tra.right=node;
node.right=temp;
}
}
}
}
{
}
{
if(right!=null)
TreetoList(right);``````

}}

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

``````public void DegenerateTree(TreeNode root)
{
if (root == null)
return;

var p = root;
var stack = new Stack<TreeNode>();

while (p != null)
{
if (p.Left == null && p.Right == null)
{
if (stack.Count > 0)
{
var node = stack.Pop();
p.Right = node;
}
}
else if (p.Left != null)
{
if (p.Right != null)
stack.Push(p.Right);
p.Right = p.Left;
p.Left = null;
}
p = p.Right;
}
}``````

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

some c# code. Suppose it works ok.

``````static Tuple<Node, Node> Transform(Node node)
{
Node begin, end;

if (node.Left != null)
{
var result = Transform(node.Left);
begin = result.Item1;
result.Item2.Right = node;
node.Left = null;
}
else
{
begin = node;
}

if (node.Right != null)
{
var result = Transform(node.Right);
end = result.Item2;
node.Right = result.Item1;
}
else
{
end = node;
}
return new Tuple<Node, Node>(begin,end);
}``````

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

Assumed BST?

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

``````static class Node {
int value;
Node left;
Node right;

public Node() {}
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}

static class Result {
Node tail;
}

static Result transform(Node root) {
if (root == null) return null;
Result result = new Result();
result.tail = root;
if (root.left != null) {
Result t = transform(root.left);
t.tail.right = root;
root.left = null;
}
if (root.right != null) {
Result t = transform(root.right);
result.tail = t.tail;
}
return result;
}``````

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

Assumed BST?

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

``````/* BST to link List */

struct node_t{
int data;
struct node_t *left;
struct node_t *right;
}

node_t *mergeLists(node_t *left, node_t *node, node_t *right)
{
assert(node != NULL);

/* merge left and node */
if(left!=NULL){
while(left->next != NULL){
left = left->right;
left->right = NULL;
}
left->next=node;
}else{
}

/* merge node and right */
node->next=right;
}

node_t *convertToList(node_t *node)
{
if(NULL == node)
return NULL;

node_t *left = convertToList(node->left);
node_t *right = convertToList(node->right);

return mergeLists(left, node, right);
}``````

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

``````/* BST to Double Link List */

struct node_t{
int data;
struct node_t *left;
struct node_t *right;
}

node_t *mergeDLists(node_t *left, node_t *node, node_t *right)
{
assert(node != NULL);

/* merge left and node */
if(left!=NULL){
while(left->right != NULL){
left = left->right;
}
left->right = node;
node->left = left;
}else{
}

/* merge node and right */
node->right=right;
right->left = node;
}

node_t *convertToDList(node_t *node)
{
if(NULL == node)
return NULL;

node_t *left = convertToList(node->left);
node_t *right = convertToList(node->right);

return mergeLists(left, node, 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.