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
Answer

Interview Answer

8 Answers

2

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

Jay on Aug 4, 2011
1

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

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

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

void doubleLink(Node *pRoot)
{
    stack stack;
    Node *pFirst = NULL;
    Node *pPrev = NULL;

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

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

donutello on Sep 10, 2011
0

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

TreeNode* MakeCircularDoublyLinked(TreeNode* head)
{
    DoublyLink(head, head);
    return MakeCircular(head);
}

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

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

    rightEnd->next = leftEnd;
    leftEnd->prev = rightEnd;

    return leftEnd;
}

listNode* DoublyLink(TreeNode* current, TreeNode* prevTreeNode)
{
    if (current == NULL)
    {
        return NULL;
    }

    current->left = DoublyLink(current->left, current);
    if (current->left != NULL)
    {
        current->left->right = current;
    }
    current->right = DoublyLink(current->right, current);
    if (current->right != NULL)
    {
        current->right->left = current;
    }

    if (prevTreeNode->left == current)
    {
        // we are processing the left subtree, return the rightmost
        // element to the parent
        while (current->next != NULL)
        {
            current = current->next;
        }
    }
    else if (prevTreeNode->right == current)
    {
        // we are processing the right subtree, return the leftmost
        // element to the parent
        while (current->prev != NULL)
        {
            current = current->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 && node.left != null)
            {
                s.push(node);
                node = node.left;
            }
            else
            {
                // Perform the linking
                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* head;

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

    if(l != NULL) {
        head = l;
        head->lft = nd;
        nd->lft = r;
    }
    else {
        head = nd;
        head->lft = r;
    }

    return head;
}

void print_list(bst_node* bst) {
    bst_node* head = bst;

    while(head != NULL) {
        cout val lft;
    }
}

Hussein on Apr 6, 2012
0

void BinTree::convert()
{
    Node * head, * tail;
    convert_to_dlist(root, head, tail);
    Node * current = head;
    while(current != tail)
    {
        cout val right;
    }
    cout val val left;
    }
    cout val left, lhead, ltail);
    convert_to_dlist(node -> right, rhead, rtail);
    if(lhead == NULL && rhead == NULL)
    {
        head = node;
        tail = node;
        head -> left = head;
        head -> right = head;
    }
    else if(lhead == NULL && rhead != NULL)
    {
        head = node;
        head -> right = rhead;
        rhead -> left = head;

        tail = rtail;
        head -> left = tail;
        tail -> right = head;
    }
    else if(lhead != NULL && rhead == NULL)
    {
        head = lhead;
        head -> left = node;
        node -> right = head;

        tail = node;
        tail -> left = ltail;
        ltail -> right = tail;
    }
    else
    {
        head = lhead;
        tail = rtail;
        ltail -> right = node;
        node -> left = ltail;
        node -> right = rhead;
        rhead -> left = node;
        head -> left = tail;
        tail -> right = head;
    }
    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

Add Answers or Comments

To comment on this, Sign In or Sign Up.