Converting a BST to circular Doubly linked list

Yesterday, while browsing on internet I landed up on a good, yet very basic DS and algorithm problem. Its not that difficult to solve, but can go a little weird if you miss out or go wrong at 1 or 2 pointer changes. ok, so here goes the problem:

Given a Binary search Tree ( I assume here, that most of you are aware of it, by now at least. Others, may like to read this before reading this problem further). You have to create a recursive function, which takes a BST and returns the corresponding Circular Doubly linked list.

Ok. Lets consider a sample BST (Binary Search Tree)

    a(5)
   /   \
  b(3)  c(6)
 /    \    \
d(2) e(4)   f(7)

[Note: the letters 'a','b'... are the names given to the nodes and the value in the parenthesis indicates the numeric data of that node]

Now our objective is to make a recursive function which takes the above tree as input and returns a circular doubly linked list, somewhat like this:-

d(2)==b(3)==e(4)==a(5)==c(6)==f(7)==d(2) ( its circular)

here the 'left' and 'right' pointers of the Node of the BST, will be treated analogous to 'previous' and 'next' in the linked list.

A little thought to the problem, and I came up with following solution. Heres the intended function's pseudo code:-

function bstToList(root)
{
 //for leaf node return itself ( case 1)
 if (root.left == root and root.right == root)
     return root

 //no left subtree exist (case 2)
 else if (root.left == root)
 {
     head2 = bstToList(root.right) //call recursively
     root.right = head2
     head2.left.right = root       //head2.left refers to the last node in the list
     root.left = head2.left
     head2.left = root
     return root
 }

 //no right subtree exist (case 3)
 else if (root.right == root)
 {
     head1 = bstToList(root.left) //call recursively
     root.left = head1.left   //head1.left refers to the last node in the list
     head1.left.right = root
     root.right = head1
     head1.left = root
     return head1
 }

 //both left and right subtrees exist (case 4)
 else
 {            
     h1 = bstToList(root.left)  //call recursively  and find the head nodes of both sublists
     h2 = bstToList(root.right)

     l1 = h1.left               //find last nodes of the sublists
     l2 = h2.left

     h1.left = l2              //join the ends of both sublists
     l2.right = h1

     l1.right = root           //insert the root to the end of left sublist
     root.left = l1

     root.right = h2           //insert the right sublist to the right of root
     h2.left = root

     return h1                 //return the head node

   }
} //function ends

As evident, the function considers 4 major cases:-
1. When the current node(root) is a leaf node( a leaf node is one with no children)
2. When there exists no left subtree/child
3. When there exists no right subtree/child
4. When there exists both left and right subtree/child

In every call the function tries to append the current node to the already formed doubly linked lists at the appropriate position.( it can be easily figured out in the above code in case 4)

Here goes the complete implementation(its in Python, but can be understood, inspite of my terrible coding style):-

class node:
 ''' class to represent a node of BST/ linked list'''
 def __init__(self, data):
     self.data = data
     self.left = self
     self.right = self

def printBST(root):
 '''prints the BST in an inorder sequence'''
 if root.left == root or root.right == root:
     print root.data, " ",
 else:
     printBST(root.left)
     print root.data, " ",
     printBST(root.right)

def printList(head):
 '''prints the linked list in both directions
  to test whether both the 'next' and 'previous' pointers are fine'''
 #print forward direction
 h = head
 print '[%d]' % (h.data),
 h = h.right
 while h != head:
     print '[%d]' % (h.data),
     h = h.right

 print ""
 #print in reverse direction
 h = head.left
 print '[%d]' % (h.data),
 h = h.left
 while h != head.left:
     print '[%d]' % (h.data),
     h = h.left


def bstToList(root):
 '''
 main function to take the root of the BST and return the head of the
 doubly linked list
  '''

 #for leaf node return itself
 if root.left == root and root.right == root:
     return root

 elif root.left == root:   #no left subtree exist
     h2 = bstToList(root.right)
     root.right = h2
     h2.left.right = root
     root.left = h2.left
     h2.left = root
     return root

 elif root.right == root:   #no right subtree exist
     h1 = bstToList(root.left)
     root.left = h1.left
     h1.left.right = root
     root.right = h1
     h1.left = root
     return h1

 else:                       #both left and right subtrees exist
     h1 = bstToList(root.left)
     h2 = bstToList(root.right)

     l1 = h1.left      #find last nodes of the lists
     l2 = h2.left

     h1.left = l2
     l2.right = h1

     l1.right = root
     root.left = l1

     root.right = h2
     h2.left = root

     return h1




if __name__ == "__main__":

 #create the sample BST
 root = a = node(5)
 b = node(3)
 c = node(6)
 d = node(2)
 e = node(4)
 f = node(7)

 a.left, a.right = b, c
 b.left, b.right = d, e
 c.right = f

 printBST(root)

 print "\ncreating to double linked list"
 head = bstToList(root);

 printList(head)

I am sure this is not the best way to go, but it surely solve the problem in a recursive way. Comments welcome
Happy Coding! :~) @_@