# Circular Doubly Linked List: Recursiveby Isai Damier, Android Engineer @ Google

```  #=====================================================================
# Author: Isai Damier
# Title: BST to Circular Doubly Linked List (Recursive)
# Project: geekviewpoint
# Package: algorithms
#
# Description: Convert a BST into a circular doubly LinkedList.
#
# Technical Details: This is a recursive method for converting a BST
#   into a cyclic doubly LinkedList. This is not the only recursive
#   method around. This method however inculcates the truth that python
#   does not pass by reference. The lists head = {None} and
#   tail = {None} are necessary handles for tracking both the head and
#   the tail of the LinkedList. (A good alternative might be to have
#   the recursive function return a value.)
#
#=====================================================================

class BST( object ):

def __init__( self ):
self.root = None

def getRoot( self ):
return self.root

def _toCircularDoublyLinkedList_recursive( self, n, h, t ):
if n is None:
return

# left
if n.left is not None:

# visit
if h[0] is None:
h[0] = t[0] = n
else:
t[0].right = n # link right
n.left = t[0] # link left
t[0] = t[0].right # reassign tail

```
```import unittest
from algorithms.BST import BST
from cStringIO import StringIO
import sys
class Test( unittest.TestCase ):
#====================================================================
# Description: Test the toCircularDoublyLinkedList_recursive function.
#   The trick here is to avoid falling into an endless loop as the tree
#   is now a circular structure with no definite end points.
#
# Technical Details: From a testing viewpoint
#====================================================================
bst = BST()

treeTape = [200, 100, 300, 50, 150, 250, 350, 25, 75, 125,
175, 225, 275, 325, 375, 35, 212, 312, 400]
# set expectation
ino = [35, 25, 75, 50, 125, 175, 150, 100, 212, 225, 275, 250,
312, 325, 400, 375, 350, 300, 200]
ino.sort() # mergesort: like inorder

for i in treeTape:

self.assertEquals( len( treeTape ), bst.size() ) # has correct size