Circular Doubly Linked List: Recursive
by Isai Damier, Android Engineer @ Google

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
  #=====================================================================
  # 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 );