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

/**************************************************************************
 * 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.
 *
 *************************************************************************/ 
 public Node toCircularDoublyLinkedList_iterative() {
  Node head = null, tail = null;
  Stack<Node> stack = new Stack<Node>();
  Node n = root;
  //inorder loop
  while (null != n || !stack.isEmpty()) {
    //traverse left
    if (null != n) {
      stack.push(n);
      n = n.left;
    } else {//visit
      n = stack.pop();
      if (null == head) {
        head = tail = n;
      } else {
        tail.right = n;//link right
        n.left = tail;//link left
        tail = tail.right;//reassign tail
      }
      //traverse right
      n = n.right;
    }//else
  }//while

  //make circular
  if (null != head) {
    tail.right = head;
    head.left = tail;
  }//if
  return head;
}

import org.junit.Test;
import static org.junit.Assert.*;

public class BSTTest {

 /*****************************************************************
   * Function: toCircularDoublyLinkedList_iterativeTest
   * Inputs: ;
   * 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.
   *
   ****************************************************************/
  @Test
  public void testToCircularDoublyLinkedList_iterative() {
    System.out.println(""toCircularDoublyLinkedList_iterative"");
    BST bst = new BST();
    int[] treeTape = {200, 100, 300, 50, 150, 250, 350, 25, 75, 125,
      175, 225, 275, 325, 375, 35, 212, 312, 400};
    assertNull(bst.toCircularDoublyLinkedList_iterative());
    //set expectation
    Integer[] ino = {35, 25, 75, 50, 125, 175, 150, 100, 212, 225, 275, 250,
      312, 325, 400, 375, 350, 300, 200};
    Arrays.sort(ino);//mergesort: like inorder

    //load data into tree
    for (int i : treeTape) {
      bst.add(i);
    }
    assertEquals(treeTape.length, bst.size());//has correct size

    //test toCircularDoublyLinkedList_iterative
    Node head = bst.toCircularDoublyLinkedList_iterative();
    Node tmp = head;
    int i = 0;
    while (true) {
      assertEquals((int) ino[i++], (int) tmp.data);
      tmp = tmp.right;
      if (tmp.right == head) {
        break;
      }
    }//while

    //calling on size() below would be disastrous: circular!
    assertEquals(i + 1, treeTape.length);
  }
}