Detailed analysis and solution is available in the following blog: http://codercareer.blogspot.com/2011/09/interview-question-no-1-binary-search.html

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 }

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; } }

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; }

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; }

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; } } }

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)