how to draw circular doubly linked list?

Ordered Tree to Circular Doubly link list: A non-recursive function treeToList (Node root) that takes an ordered binary tree and rearranges the internal pointers to make a circular doubly linked list out of the tree nodes?

• In order to understand about the Node's structure of a tree Node, please  follow the link given below. The "previous" pointers should be stored in the "small" field and the "next" pointers should be stored in the "large" field. The list should be arranged so that the nodes are in increasing order. Return the head pointer to the new list. The operation can be done in O(n) time. This is most famous and advance problem on tree and linked list. Reference : http://cslibrary.stanford.edu/109/TreeListRecursion.html.

• Answer:

  That's kind of fun. If you do it manually on a sheet of paper you notice it's just clockwise rotations of the left branch of sub-trees starting at the root  iterating down to  the rightmost leaf. Start at the root and rotate the left branch making it the the new sub-tree root until there is no left branch. Repeat for each successive right node.  Point the previous sub tree root larger field at the current sub-tree root.  Point its smaller field at the previous subtree root.  Set root on the first iteration.  Make the list circular at the end. Ex: #include <assert.h> #include <stdlib.h> struct node { int value; struct node *left, *right; }; // Reurns new root or NULL for no rotation static struct node * rotate_clockwise(struct node *in) { struct node *rightmost, *ret; for (ret = rightmost = in->left; rightmost && rightmost->right; rightmost = rightmost->right) { } if (rightmost) { rightmost->right = in; in->left = NULL; } return ret; } struct node * tree_to_list(struct node *in) { struct node *root, *prev, *current, *tmp; for (root = prev = NULL, current = in; current; prev = current, current = current->right) { for (tmp = current; tmp; current = tmp, tmp = rotate_clockwise(tmp)) { } assert(!current->left); assert(!root == !prev); if (!root) { root = current; } else { prev->right = current; } // still a legal tree and singly-linked list without this current->left = prev; } if (root) { root->left = prev; prev->right = root; } return root; } While the O(N) traversals down the new tree right branch in the main loop and  left sub-tree right branches for the rotation smell  like O(N^2) each node is visited at most twice - once moving along the root tree's right branch, and once from the left or right when rotation is required making O(N).