Facebook Interview Question: Convert a binary search tree ... | Glassdoor

## Interview Question

Software Engineer Interview Palo Alto, CA

# Convert a binary search tree to a sorted, circular

, doubly-linked list, in place (using the tree nodes as the new list nodes).
Tags:
c algorithms data-structures

2

Recursively:
- convert the left subtree (returns a dbl-linked list (DLL) with a head ptr &amp; tail ptr)
- convert the right subtree (same)
- connect the left DLL tail to the right DLL head bi-directionally

Jay on Aug 4, 2011
1

struct StackEntry
{
Node *pNode;
bool fVisit;
};

inline void linkNodes(Node *pLeft, Node *pRight)
{
pLeft-&gt;pNext = pRight;
pRight-&gt;pPrev = pLeft;
}

inline void visitNode(Node **ppFirst, Node **ppPrev, Node *pNode)
{
if(ppPrev == NULL)
{
*ppFirst = pNode;
*ppPrev = pNode;
}
else
{
*ppPrev = pNode;
}
}

{
stack stack;
Node *pFirst = NULL;
Node *pPrev = NULL;

StackEntry rootEntry = {pRoot, false};
stack.push(rootEntry);

while(stack.size() != 0)
{
StackEntry &amp;top = stack.top();
stack.pop();
if(top.fVisit)
{
visitNode(&amp;pFirst, &amp;pPrev, top.pNode);
}
else
{
StackEntry entry;
if(pNode-&gt;pLeft != NULL)
{
entry.pNode = pNode-&gt;pLeft;
entry.fVisit = false;
stack.push(entry);
}
entry.pNode = pNode;
entry.fVisit = true;
stack.push(entry);
if(pNode-&gt;pRight != NULL)
{
entry.pNode = pNode-&gt;pRight;
entry.fVisit = false;
stack.push(entry);
}
}
}
if(pPrev != NULL)
{
}
}

donutello on Sep 10, 2011
0

class TreeNode
{
TreeNode* left;
TreeNode* right;
int value;
}

{
}

TreeNode* MakeCircular(TreeNode* node)
{
TreeNode* leftEnd = node;
while (leftEnd-&gt;prev != NULL)
{
leftEnd = leftEnd-&gt;prev;
}

listNode* rightEnd = node;
while (rightEnd-&gt;prev != NULL)
{
rightEnd = rightEnd-&gt;prev;
}

rightEnd-&gt;next = leftEnd;
leftEnd-&gt;prev = rightEnd;

return leftEnd;
}

{
if (current == NULL)
{
return NULL;
}

if (current-&gt;left != NULL)
{
current-&gt;left-&gt;right = current;
}
if (current-&gt;right != NULL)
{
current-&gt;right-&gt;left = current;
}

if (prevTreeNode-&gt;left == current)
{
// we are processing the left subtree, return the rightmost
// element to the parent
while (current-&gt;next != NULL)
{
current = current-&gt;next;
}
}
else if (prevTreeNode-&gt;right == current)
{
// we are processing the right subtree, return the leftmost
// element to the parent
while (current-&gt;prev != NULL)
{
current = current-&gt;prev;
}
}

return current;
}

PrinceBoroujerdi on Oct 8, 2011
2

Detailed analysis and solution is available in the following blog:

http://codercareer.blogspot.com/2011/09/interview-question-no-1-binary-search.html

Harry on Nov 13, 2011
0

Java, non-recursive. O(n) time, O(1) space:

import java.util.Stack;

public class TreeToCircList
{
public static class Node
{
public Node left = null;
public Node right = null;
public int data;
}

public void convert(Node node)
{
boolean leftChecked = false;
Node prev = null;
Node start = null;
Stack s = new Stack();

while(node != null)
{
if(leftChecked == false &amp;&amp; node.left != null)
{
s.push(node);
node = node.left;
}
else
{
node.left = prev;
if(prev != null) prev.right = node;
else start = node; // Mark start of the list
prev = node;

if(node.right != null)
{
node = node.right;
leftChecked = false;
}
else if(s.empty() == false)
{
node = s.pop();
leftChecked = true;
}
else
{
node = null;
}
}
}

// Find the first node to link with the last node
if(prev != null)
{
start.left = prev;
prev.right = start;
}
}
}

Aaron on Nov 26, 2011
0

Thanks to recursion .. this is a sorted linked list .. to make it circular just make a pointer from the last to the head. :)

bst_node* getList(bst_node* nd) {
if(nd == NULL) return NULL;

bst_node* l = getList(nd-&gt;lft);
bst_node* r = getList(nd-&gt;rt);

if(l != NULL) {
nd-&gt;lft = r;
}
else {
}

}

void print_list(bst_node* bst) {

cout val lft;
}
}

Hussein on Apr 6, 2012
0

void BinTree::convert()
{
while(current != tail)
{
cout val right;
}
cout val val left;
}
{
tail = node;
}
{

tail = rtail;
}
{

tail = node;
tail -&gt; left = ltail;
ltail -&gt; right = tail;
}
else
{
tail = rtail;
ltail -&gt; right = node;
node -&gt; left = ltail;
}
return;
}

Anonymous on Jul 25, 2012
1

Solution by recursive in-order traversal.

To make code simply I did not make linked list circular. It can be done by simply modification to return both head and tail and connect them outside recursion.

Node Convert(Node root)
{
if (root == null) return null;
Node last = null;
return InOrder(root, ref last);
}

Node InOrder(Node node, ref Node last)
{
Node left = null;
if (node.Left != null)
left = InOrder(node.Left, ref last);
node.Left = last;
if (last != null)
last.Right = node;
last = node;
if (node.Right != null)
InOrder(node.Right, ref last);
return left ?? node; // return the smallest node which will be the head
}

Jerry on Oct 22, 2012