CareerCup

BST to Circular DLL
static BSTNode prev, head;

	public static BSTNode convetToCLL(BSTNode root) {
		if (root == null)
			return null;
		convetToCLL(root.getLeft());
		if (prev == null) { // first node in list
			head = root;
		} else {
			prev.setRight(root);
			root.setLeft(prev);
		}
		prev = root;
		convetToCLL(root.getRight());
		if (prev.getRight() == null) { // last node in list
			head.setLeft(prev);
			prev.setRight(head);
		}
		return head;
	}

BST to Doubly Linked List
static BSTNode prevDLL, headDLL;
	public static BSTNode convetToDLL(BSTNode root) {
		if (root == null)
			return null;
		convetToDLL(root.getLeft());
		if (prevDLL == null) { 
			headDLL = root;
		} else {
			prevDLL.setRight(root);
			root.setLeft(prevDLL);
		}
		prevDLL = root;
		convetToDLL(root.getRight());
		return headDLL;
	}

Basic idea: If we could get a doubly linked list + it's head + it's tail, we could use recursion.

Recursively create list of left subtree, of right subtree and insert the root in the middle, returning the head of left tree and tail of right tree.

Pseudo code...

DLL & TreeToDLL(Tree & t) {
    
     // do base cases, left out.

     DLL l = TreeToDLL(t.Left);
     DLL r = TreeToDLL(t.Right);

     LLNode n = new LLNode(t.value);

     return Concat(l, n, r);
}

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

Use logic of inorder traversal

void ConvertTreeToDLL(TreeNode *currentNode) {
	if(currentNode) {
		// Go all the way to left most
		ConvertTreeToDLL(currentNode -> left);
		
		// Create the list
		
		// If head is null, create it
		if(!head) {
			head = (DLL *) malloc(sizeof(DLL));
			head -> value = currentNode -> value;
			head -> left = 0;
			head -> right = 0;
			cachedPrevNode = head;
		}
		
		// else add it to current list
		else {
			newNode = (DLL *) malloc(sizeof(DLL));
			newNode -> value = currentNode -> value;
			newNode -> left = cachedPrevNode;
			cachedPrevNode -> right = newNode;
			cachedPrevNode = newNode;
		}
		
		// Go all the way to rigt most
		ConvertTreeToDLL(currentNode -> right);
		
	}
}

btree* attachList(btree *a, btree* b)
{
        btree *temp;
        if(a == 0)
                return b;
        if(b == 0)
                return a;

        a->left->right = b;
        b->left->right = a;
        temp = a->left;
        a->left = b->left;
        b->left = temp;
        return a;
}

btree* convertToList(btree *p)
{
        btree *pLeft, *pRight;
        if(p == 0)
                return 0;

        pLeft = convertToList(p->left);
        pRight = convertToList(p->right);
        p->left = p->right = p;
        p = attachList(pLeft, p);
        p = attachList(p, pRight);
        return p;
}

TL(n, b)
	if(n == NULL)
		return NULL
	n->l = TL(n->l, 0)
	n->r = TL(n->r, 1)
	if(b == 0)
		return n->r
	else
		return n->l

Improved one..

TL(n, b)
	if(n == NULL)
		return NULL
	a = TL(n->l, 0)
	n->l = a
	a->r = n
	b = TL(n->l, 0)
	n->r = b
	b->l = n
	if(b == 0)
		if(n->r)
			return n->r
		else
			return n
	else
		if(n->l)
			return n->l
		else
			return n