#=====================================================================
# 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 ) )
