Facebook Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
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;
}
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
l_head = l_tail = r_head = r_tail = None
if node._left:
l_head, l_tail =listfy(node._left)
if node._right:
r_head, r_tail = listfy(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:
l_head = node
# 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.
if r_head:
node._right = r_head
r_head._left = node
else:
r_tail = node
return l_head, r_tail
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 *head;
Node *tail;
Node *current;
modInorder(treeHead, current, head, tail);
tail -> right = *head;
head -> left = *tail;
}
modInorder(Node n, Node *current, Node * head, Node * tail) {
if (n == NULL) {
return;
}
Node previous;
if (*head == NULL) {
head = &n;
}
tail = &n;
previous = modInorder(n.left, current);
current -> right = n;
current = &n;
current -> left = previous;
modInorder(n.right, current)
}
#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;
}
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)
{
Node *head = convert(root);
Node *tail = head;
if (!head)
return NULL;
while (head->left || tail->right)
{
if (head->left) head = head->left;
if (tail->right) tail = tail->right;
}
head->left = tail;
tail->right = head;
return head;
}
class Node
{
Node* left;
Node* right;
int val;
}
Node* f(Node* root)
{
if(!root) return nullptr;
Node* head = nullptr;
ff(root, &head);
return head;
}
void ff(Node* root, Node** head)
{
if(root->left)
{
ff(root->left, head);
}
Node* right = root->right;
add(head, root);
if(right)
{
ff(right, head);
}
}
void add(Node** head, Node* newNode)
{
if(*head == nullptr)
{
*head = newNode;
*head->right = *head;
*head->left = *head;
return;
}
newNode->left = head->left;
newNode->right = head;
head->left = newNode;
}
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;
static Node *head;
if (root == NULL)
{
return;
}
convertToCircularDLL(root->left);
if (prev == NULL)
{ // first node in list
head = root;
}
else
{
prev->right = root;
root->left = prev;
}
prev = root;
convertToCircularDLL(root->right);
if (prev->right == NULL)
{ // last node in list
head->left = prev;
prev->right = head;
}
}
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;
convertToCircularDLL(root, &prev, &head);
TreeNode[] registr = new TreeNode[2];
convertBinaryTreeToCL(t1, registr);
public static void convertBinaryTreeToCL(TreeNode node, TreeNode[] register) {
if(node == null)
return ;
convertBinaryTreeToCL(node.left, register);
TreeNode head = register[0];
TreeNode prev = register[1];
if(head == null) {
register[0] = head = node;
}
else {
node.left = prev;
prev.right = node;
}
register[1] = prev = node;
convertBinaryTreeToCL(node.right, register);
if(prev.right == null) {
prev.right = head;
head.left = prev;
}
}
#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;
}
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;
}
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* head = 0;
node* tail = 0;
void inorder_tree2(node* r)
{
if (!r)
return;
inorder_tree2(r->left);
if (!head)
{
head = tail = r;
} else {
tail->right = r;
tail = r;
}
inorder_tree2(r->right);
}
node * flat_tree(node *root)
{
inorder_tree2(root);
node * cur = head;
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;
return head;
}
///
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;
if (*newHead == NULL) {
*newHead = newNode;
newNode->left = newNode->right = newNode;
} else {
Node *end = newHead->left;
end->right = newNode;
newNode->left = end;
newNode->right = newHead;
}
if (root->right != NULL) {
BinaryTreeToLL(root->right);
}
}
\\\
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.
- dph March 30, 2015