Facebook Interview Question
Software EngineersTeam: Multiple
Country: United States
Interview Type: Written Test
private static ListNode convertToList(TreeNode node) {
if (node == null)
return null;
ListNode head = new ListNode(-1);
ListNode tail = treeToList(node, head);
head = head.next;
head.prev = tail;
tail.next = head;
return head;
}
private static ListNode treeToList(TreeNode n, ListNode tail) {
if (n == null)
return tail;
tail = treeToList(n.left, tail);
tail.next = new ListNode(n.data);
tail.next.prev = tail;
tail = tail.next;
tail = treeToList(n.right, tail);
return tail;
}
private static ListNode convertToList(TreeNode node) {
if (node == null)
return null;
ListNode head = new ListNode(-1);
ListNode tail = treeToList(node, head);
head = head.next;
head.prev = tail;
tail.next = head;
return head;
}
private static ListNode treeToList(TreeNode n, ListNode tail) {
if (n == null)
return tail;
tail = treeToList(n.left, tail);
tail.next = new ListNode(n.data);
tail.next.prev = tail;
tail = tail.next;
tail = treeToList(n.right, tail);
return tail;
}
In Scala:
def binTreeToList(node: TreeNode): TreeNode = {
if (node == null) {
node
} else {
var newNode = binTreeToListUtil(node)
while (newNode.left != null) newNode = newNode.left
newNode
}
}
def binTreeToListUtil(node: TreeNode): TreeNode = {
if (node != null) {
if (node.left != null) {
var left = binTreeToListUtil(node.left)
while (left.right != null) left = left.right
left.right = node
node.left = left
}
if (node.right != null) {
var right = binTreeToListUtil(node.right)
while (right.left != null) right = right.left
right.left = node
node.right = right
}
}
node
}
class BinaryTreeNode():
def __init__(self,value=None):
self.value = value
self.left = None
self.right = None
def print_tree(self):
print self.value
if self.left:
self.left.print_tree()
if self.right:
self.right.print_tree()
class ListNode():
def __init__(self,value):
self.value = value
self.next = None
self.prev = None
def print_list1(self):
node = self
while node:
print node.value
node = node.next
def print_list2(self):
node = self
while node.next:
node = node.next
while node:
print node.value
node = node.prev
def print_list(self):
print self.value
if self.next:
self.next.print_list()
def convert_to_list(tree):
if not tree:
return None
head, _ = _convert_to_list(tree, None)
return head
def _convert_to_list(tree, tail):
if not tree:
return None, None
new_tail = ListNode(tree.value)
if tail:
tail.next = new_tail
new_tail.prev = tail
new_tail.next, last1 = _convert_to_list(tree.left, new_tail)
if not last1:
last1 = new_tail
last1.next,last2 = _convert_to_list(tree.right, last1)
if not last2:
last2 = last1
return new_tail,last2
t = BinaryTreeNode(1)
t.left = BinaryTreeNode(2)
t.left.left = BinaryTreeNode(2.2)
t.left.left.left = BinaryTreeNode(2.22)
t.right = BinaryTreeNode(3)
t.right.right = BinaryTreeNode(4)
t.right.left = BinaryTreeNode(5)
print "-"*100
t.print_tree()
l = convert_to_list(t)
print "-"*100
l.print_list1()
print "-"*100
l.print_list2()
I used a BST to generate BT as input of this example. I do not relay at any time on the fact the input is a BST I am making the doubled linked list. Complexity is O(n) where n is number of nodes in the tree.
class BTNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
class BSTree:
def __init__(self):
self.root = None
@staticmethod
def _find(key, node):
if node.key == key:
return key
elif node.key > key:
if node.left is not None:
return BSTree._find(key, node.left)
return node
else:
if node.right is not None:
return BSTree._find(key, node.right)
return node
def find(self, key):
if self.root is None:
raise IndexError('find from empty tree')
return self._find(key, self.root)
def insert(self, key):
if self.root is None:
self.root = BTNode(key)
return
node = self.find(key)
if node.key > key:
node.left = BTNode(key)
elif node.key < key:
node.right = BTNode(key)
@staticmethod
def _rexplore(node, preorder, inorder, postorder):
if node is None:
return
if preorder is not None:
preorder(node)
BSTree._rexplore(node.left,
preorder, inorder, postorder
)
if inorder is not None:
inorder(node)
BSTree._rexplore(node.right,
preorder, inorder, postorder
)
if postorder is not None:
postorder(node)
def rexplore(self,
preorder=None, inorder=None, postorder=None
):
if self.root is None:
return
BSTree._rexplore(self.root,
preorder, inorder, postorder
)
@staticmethod
def _iexplore(node, preorder, inorder, postorder):
stack = [(False, False, node)]
while len(stack) > 0:
expleft, expright, node = stack.pop()
if not expleft:
if preorder is not None and not expright:
preorder(node)
if node.left is not None:
stack.append((True, expright, node))
stack.append((False, False, node.left))
continue
if not expright:
if inorder is not None:
inorder(node)
if node.right is not None:
stack.append((expleft, True, node))
stack.append((False, False, node.right))
continue
if postorder is not None:
postorder(node)
def iexplore(self,
preorder=None, inorder=None, postorder=None
):
if self.root is None:
return
BSTree._iexplore(self.root,
preorder, inorder, postorder
)
def print_node(node):
if node is None:
print('null')
print('key = {}'.format(node.key))
keys = [4,1,3,5,2,6,7]
tree = BSTree()
for key in keys:
tree.insert(key)
tree.rexplore(postorder=print_node)
print()
tree.iexplore(postorder=print_node)
# Output
# 7 <- 1 -> 2
# 1 <- 2 -> 3
# 2 <- 3 -> 4
# 3 <- 4 -> 5
# 4 <- 5 -> 6
# 5 <- 6 -> 7
# 6 <- 7 -> 1
This is the correct entry. I made a mistake in a previous post.
I used a BST to generate BT as input of this example. I do not relay at any time on the fact the input is a BST I am making the doubled linked list. Complexity is O(n) where n is number of nodes in the tree.
class BTNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
class BSTree:
def __init__(self):
self.root = None
@staticmethod
def _find(key, node):
if node.key == key:
return key
elif node.key > key:
if node.left is not None:
return BSTree._find(key, node.left)
return node
else:
if node.right is not None:
return BSTree._find(key, node.right)
return node
def find(self, key):
if self.root is None:
raise IndexError('find from empty tree')
return self._find(key, self.root)
def insert(self, key):
if self.root is None:
self.root = BTNode(key)
return
node = self.find(key)
if node.key > key:
node.left = BTNode(key)
elif node.key < key:
node.right = BTNode(key)
class DLNode:
def __init__(self, value):
self.value = value
self.next = None
self.prev = None
def btree_to_dllist(node):
head = None
tail = None
def inorder(node):
nonlocal head
nonlocal tail
if tail is None:
tail = DLNode(node.key)
head = tail
return
curr = DLNode(node.key)
tail.next = curr
curr.prev = tail
tail = curr
def explore(node):
if node is None:
return
explore(node.left)
inorder(node)
explore(node.right)
explore(node)
if head == tail:
return head
tail.next = head
head.prev = tail
return head
def print_list(node):
if node.prev is None or node.next is None:
print('None <- {} -> None'.format(node.value))
return
print('{} <- {} -> {}'.format(
node.prev.value, node.value, node.next.value
))
head = node
node = node.next
while node != head:
print('{} <- {} -> {}'.format(
node.prev.value, node.value, node.next.value
))
node = node.next
keys = [4,1,3,5,2,6,7]
tree = BSTree()
for key in keys:
tree.insert(key)
dllist = btree_to_dllist(tree.root)
print_list(dllist)
# Output
# 7 <- 1 -> 2
# 1 <- 2 -> 3
# 2 <- 3 -> 4
# 3 <- 4 -> 5
# 4 <- 5 -> 6
# 5 <- 6 -> 7
# 6 <- 7 -> 1
#include <memory>
#include <iostream>
#include <tuple>
struct BinaryTree
{
using btp = BinaryTree*;
BinaryTree(
int aValue,
btp aLeft = nullptr,
btp aRight = nullptr):
value(aValue), left(aLeft), right(aRight)
{};
int value;
btp left;
btp right;
};
using btp = BinaryTree::btp;
struct Node
{
using llp = Node*;
Node(int aValue, llp aLast = nullptr, llp aNext = nullptr)
:value(aValue), last(aLast), next(aNext)
{ // fix links from other node's perspective.
if (last)
{ last->next = this; }
if (next)
{ next->last = this; }
}
int value;
llp last;
llp next;
};
using llp = Node::llp;
std::pair<llp, llp> trav_down(btp aTreeNode, llp aLastNode)
{
if (!aTreeNode) { return {aLastNode, nullptr};}
llp last = aLastNode;
llp first = nullptr;
if (aTreeNode->left)
{
std::tie(last, first) = trav_down(aTreeNode->left, last);
}
last = new Node(aTreeNode->value, last);
if (!first)
{ first = last; }
if (aTreeNode->right)
{
std::tie(last, std::ignore) = trav_down(aTreeNode->right, last);
}
return {last, first};
}
int main(int, char**)
{
// don't try this in production - leaks memory everywhere!
btp tree = new BinaryTree
{
4,
new BinaryTree(3,
new BinaryTree(5),
new BinaryTree(6)
),
new BinaryTree(7, new BinaryTree(6), new BinaryTree(9))
};
auto [last, first] = trav_down(tree, nullptr);
// we need it to be circular, so will have to add the link.
if (last)
{ last->next = first; }
if (first)
{ first->last = last; }
// debugging only.
std::cout<<"Printing out list forwards"<<std::endl;
{
bool first_time{true};
for (llp iter=first;iter && (first_time || iter!=first);iter = iter->next)
{
std::cout<<"Value is " << iter->value << std::endl;
first_time=false;
}
}
std::cout<<"Printing out list in reverse"<<std::endl;
{
bool first_time{true};
for (llp iter=last;iter && (first_time || iter!=last);iter = iter->last)
{
std::cout<<"Value is " << iter->value << std::endl;
first_time=false;
}
}
}
- Anonymous December 19, 2018