Circular Doubly Linked List: Iterative
by Isai Damier

  #=====================================================================
  # Author: Isai Damier
  # Title: BST to Circular Doubly Linked List (Iterative)
  # Project: geekviewpoint
  # Package: algorithms
  #
  # Time Complexity of Solution:
  #   Best = Average = Worst = O(n).
  #
  # Description: Convert a BST into a circular doubly LinkedList.
  #
  # Technical Details: This algorithm illustrates the importance of knowing
  #   how to traverse a BST iteratively. The code is elegant and simple.
  #
  #=====================================================================
 
 
class BST( object ):

  def __init__( self ):
      self.root = None


  def getRoot( self ):
    return self.root

  def toCircularDoublyLinkedList_iterative( self ):
    head, tail = None, None
    stack = LifoQueue()
    n = self.root

    # inorder loop
    while n is not None or not stack.empty():
      # traverse left
      if n is not None:
        stack.put( n )
        n = n.left
      else: # visit
        n = stack.get()
        if head is None:
          head = tail = n
        else:
          tail.right = n # link right
          n.left = tail # link left
          tail = tail.right # reassign tail
        # traverse right
        n = n.right

    # make circular
    if head is not None:
      tail.right = head
      head.left = tail;
    return head;
import unittest
from algorithms.BST import BST
from cStringIO import StringIO
import sys
class Test( unittest.TestCase ):
  #======================================================================
  # Function: toCircularDoublyLinkedList_iterativeTest
  # tapes:
  # Output: void
  #
  # Description: Test the toCircularDoublyLinkedList_iterative
  #    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_iterative( 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_iterative() )
    # 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_iterative
    head = bst.toCircularDoublyLinkedList_iterative()
    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 ) )