Circular Doubly Linked List: Recursive
by Isai Damier

  #=====================================================================
  # 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 ):
    head, tail = [None], [None]
    self._toCircularDoublyLinkedList_recursive( self.root, head, tail )
    if head[0] is not None:
      tail[0].right = head[0]
      head[0].left = tail[0]

    return head[0]


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

    # left
    if n.left is not None:
      self._toCircularDoublyLinkedList_recursive( n.left, h, t )

    # 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

    self._toCircularDoublyLinkedList_recursive( n.right, h, t );
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
  #   toCircularDoublyLinkedList_iterative and
  #    toCircularDoublyLinkedList_recursive are essentially equivalent.
  #====================================================================
  def testToCircularDoublyLinkedList_recursive( self ):
    bst = BST()

    treeTape = [200, 100, 300, 50, 150, 250, 350, 25, 75, 125,
                      175, 225, 275, 325, 375, 35, 212, 312, 400]
    self.assertIsNone( bst.toCircularDoublyLinkedList_recursive() )
    # 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

    # load data into tree
    for i in treeTape:
      bst.add( i )

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

    # test toCircularDoublyLinkedList_recursive
    head = bst.toCircularDoublyLinkedList_recursive()
    tmp = head
    i = 0
    while True:
      self.assertEquals( int ( ino[i] ), int( tmp.data ) )
      i += 1
      tmp = tmp.right
      if tmp.right == head:
        break

    # calling on size() below would be disastrous: circular!
    self.assertEquals( i + 1, len( treeTape ) )