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

/*************************************************************************
 * Author: Isai Damier
 * Title: BST to Circular Doubly Linked List (Recursive)
 * 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 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 Java does not pass by
 *   reference. The arrays head = {null} and tail = {null} 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.)
 *
 *************************************************************************/ 
 public Node toCircularDoublyLinkedList_recursive() {
  Node[] head = {null}, tail = {null};
  toCircularDoublyLinkedList_recursive(root, head, tail);
  if (null != head[0]) {
    tail[0].right = head[0];
    head[0].left = tail[0];
  }
  return head[0];
}

void toCircularDoublyLinkedList_recursive(Node n, Node[] h, Node[] t) {
  if (null == n) {
    return;
  }
  //left
  if (null != n.left) {
    toCircularDoublyLinkedList_recursive(n.left, h, t);
  }
  //visit
  if (null == h[0]) {
    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
  }
  //right
  toCircularDoublyLinkedList_recursive(n.right, h, t);
}

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

public class BSTTest {

 /************************************************************************
   * 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.
   *
   ************************************************************************/
  @Test
  public void testToCircularDoublyLinkedList_recursive() {
    System.out.println(""toCircularDoublyLinkedList_recursive"");
    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_recursive());
    //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_recursive
    Node head = bst.toCircularDoublyLinkedList_recursive();
    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);
  }
}