# Circular Doubly Linked List: Iterativeby 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.
*
*************************************************************************/
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();
} else {
tail = tail.right;//reassign tail
}
//traverse right
n = n.right;
}//else
}//while

//make circular
}//if
}```
```import org.junit.Test;
import static org.junit.Assert.*;

public class BSTTest {

/*****************************************************************
* Inputs: ;
* Output: void
*
*    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
*     equivalent.
*
****************************************************************/
@Test
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};
//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

for (int i : treeTape) {
}
assertEquals(treeTape.length, bst.size());//has correct size