CareerCup

The idea is to do inorder traversal of the binary tree. While doing inorder traversal, keep track of the previously visited node in a variable say prev. For every visited node, make it next of prev and previous of this node as prev.

static Node prev,head;
    
    public static void convetToCLL(Node root){
    	if(root==null)
    		return ;
    	convetToCLL(root.left);
    	if(prev==null){  // first node in list
    		head=root;
    	}
    	else{
    		prev.right = root;
    		root.left = prev;
    	}
    	prev = root;
    	convetToCLL(root.right); 
    	if(prev.right==null){ // last node in list
    		head.left = prev;
    		prev.right = head;
    	}
    }

struct node* createNewNode(int data)
{
	//cout<<"hh"<<endl;
	struct node* tmp= new node;
	tmp->right=NULL;
	tmp->left=NULL;
	tmp->data=data;
	return tmp;
}

struct node *dLL;
struct node *head;

void treeToCLL(struct node* nodeptr)
{
	
	if(nodeptr == NULL)
		return;
	if (nodeptr->left !=NULL)
		treeToCLL(nodeptr->left);
	
	cout<<" "<<nodeptr->data<< " ";
	t_count = t_count + 1;

	struct node *temp=new node;
	temp->data=nodeptr->data;
	if(dLL!=NULL)
	{
		if(t_count < (size-1))
		{
			temp->left= dLL;
			dLL->right =temp;
			dLL=temp;
		}
		if (t_count==(size-1))
		{
			head->left=temp;
			temp->right=head;
			temp->left=dLL;
			dLL->right=temp;
		}
	}
	else
	{
		dLL=temp;
		head = dLL;
	}
	if (nodeptr->right!=NULL)
		treeToCLL(nodeptr->right);
}

}

The recursion will go down the tree, recursively changing the small and large sub-trees into lists, and then append those lists together with the parent node to make larger lists.
Separate out a utility function append(Node a, Node b) that takes two circular doubly linked lists and appends them together to make one list which is returned.
Writing a separate utility function helps move some of the complexity out of the recursive function.

/* The node type from which both the tree and list are built */
struct node {
    int data;
    struct node* small;
    struct node* large;
};
typedef struct node* Node;



/*
 helper function -- given two list nodes, join them
 together so the second immediately follow the first.
 Sets the .next of the first and the .previous of the second.
*/
static void join(Node a, Node b) {
    a->large = b;
    b->small = a;
}


/*
 helper function -- given two circular doubly linked
 lists, append them and return the new list.
*/
static Node append(Node a, Node b) {
    Node aLast, bLast;
    
    if (a==NULL) return(b);
    if (b==NULL) return(a);
    
    aLast = a->small;
    bLast = b->small;
    
    join(aLast, b);
    join(bLast, a);
    
    return(a);
}


/*
 --Recursion--
 Given an ordered binary tree, recursively change it into
 a circular doubly linked list which is returned.
*/
static Node treeToList(Node root) {
    Node aList, bList;
    
    if (root==NULL) return(NULL);

    /* recursively solve subtrees -- leap of faith! */
    aList = treeToList(root->small);
    bList = treeToList(root->large);
    
    /* Make a length-1 list ouf of the root */
    root->small = root;
    root->large = root;

    /* Append everything together in sorted order */
    aList = append(aList, root);
    aList = append(aList, bList);
    
    return(aList);



/* Create a new node */
static Node newNode(int data) {
    Node node = (Node) malloc(sizeof(struct node));
    node->data = data;
    node->small = NULL;
    node->large = NULL;
    return(node);
}


/* Add a new node into a tree */
static void treeInsert(Node* rootRef, int data) {
    Node root = *rootRef;
    if (root == NULL) *rootRef = newNode(data);
    else {
        if (data <= root->data) treeInsert(&(root->small), data);
        else treeInsert(&(root->large), data);
    }
}


static void printList(Node head) {
    Node current = head;
    
    while(current != NULL) {
        printf("%d ", current->data);
        current = current->large;
        if (current == head) break;
    }
    printf("\n");
}


/* Demo that the code works */
int main() {
    Node root = NULL;
    Node head;
    
    treeInsert(&root, 4);
    treeInsert(&root, 2);
    treeInsert(&root, 1);
    treeInsert(&root, 3);
    treeInsert(&root, 5);
    
    head = treeToList(root);
    
    printList(head);    /* prints: 1 2 3 4 5  */
    
    return(0);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// This is a modified in-order traversal adapted to this problem.
// prev (init to NULL) is used to keep track of previously traversed node.
// head pointer is updated with the list's head as recursion ends.
void treeToDoublyList(Node *p, Node *& prev, Node *& head) {
  if (!p) return;
  treeToDoublyList(p->left, prev, head);
  // current node's left points to previous node
  p->left = prev;
  if (prev)
    prev->right = p;  // previous node's right points to current node
  else
    head = p; // current node (smallest element) is head of
              // the list if previous node is not available
  // as soon as the recursion ends, the head's left pointer 
  // points to the last node, and the last node's right pointer
  // points to the head pointer.
  Node *right = p->right;
  head->left = p;
  p->right = head;
  // updates previous node
  prev = p;
  treeToDoublyList(right, prev, head);
}
 
// Given an ordered binary tree, returns a sorted circular
// doubly-linked list. The conversion is done in-place.
Node* treeToDoublyList(Node *root) {
  Node *prev = NULL;
  Node *head = NULL;
  treeToDoublyList(root, prev, head);
  return head;
}

go to left child of root.
while child has right children, rotate left. till this child has no right children any more.
link child right point back to root.
repeat above 2steps till left side become a long list. remember the left most leaf node.
now go to right child of root.
while child has left children, rotate right. till this children has no left children any more.
link child left pointer back to root.
repeat above 2 steps till right side become a long list. remember the right most leaf node.
now link left most leaf with right most leaf to become circular

inorder traversal

iterate

public TreeNode convert (TreeNode root){
		TreeNode curr = root ;
		Stack<TreeNode> stack = new Stack<> ();
		TreeNode dummyNode = new TreeNode (1);				
		TreeNode pre = null ;
		while (!stack.isEmpty() || curr != null) {
			if (curr != null) {
				stack.push(curr) ;
				curr = curr.left ;
			} else {
				//access the middle node
				TreeNode t = stack.pop() ;				
				if (pre == null) {
					if (dummyNode.next == null) {
						dummyNode.next = t ;	
					}
					pre = t ;
				} else{
					pre.next = t;
					t.prv = pre ;
					pre = t ;
				}
				curr = t.right ;
			}
		}
		return dummyNode.next ;

}

recursive

TreeNode pre = null ;
	TreeNode head = null ;
	public void convert_recursive (TreeNode root){
		if (root == null) return ;
		convert_recursive (root.left);
		if (pre == null) {
			if (head == null) head = root ;
			pre = root ;
		} else {
		   pre.next = root ;
		   root.prv = pre ;
		   pre = root ;
		}		
		convert_recursive (root.right);

}

My code

TreeNode dummy = new TreeNode(0);
	TreeNode pre = dummy ;
	public void convert(TreeNode root){
		if (root == null) return ;
		convert (root.left);
		pre.right=root;
                root.left=pre;
		convert(root.right);
}
public void convertToL(TreeNode root){
      convert(root);
      dummy.next.left=pre;
     pre.right=dummy.next;
}

Here is C++ version of solution using in-order search.

Running time is O(N).
Space complexity is O(1).

#include<iostream>
using namespace std;

struct Node {
	Node *left;
	Node *right;
	int value;
	Node(int v): value(v), left(0), right(0){}
};

class FlattenTree {
	
private:
	Node * start;
	Node * last;


	void inorder(Node * node)
	{
		if (!node)
			return;
		inorder(node->left);
		if (!start) {
			start = last = node;		
		} else {
			last->right = node;
			last = node;
		}
		inorder(node->right);
	}

public:
	
	FlattenTree():start(0), last(0){}

	Node * flatten_tree(Node * root)
	{
		inorder(root);

		//connect left to prev;
		Node * cur = start;
		Node * prev = 0;
		while(cur)
		{
			cur->left = prev;
			prev = cur;
			cur = cur->right;	
		}
		return start;
	}

};