## Facebook Interview Question

Software Engineers**Team:**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()
```

- Anonymous December 19, 2018