## Convert Binary Search Tree (BST) to Sorted Doubly-Linked List

###### Convert a BST to a sorted circular doubly-linked list in-place. Think of the left and right pointers as synonymous to the previous and next pointers in a doubly-linked list.

``````Convert BST to Circular Doubly LinkedList
// http://articles.leetcode.com/convert-binary-search-tree-bst-to/

// we could safely modify a node’s left pointer to point to the previously traversed node as we never use it once we reach a node.
// We would also need to modify the previously traversed node’s right pointer to point to the current node.
// But wait, we are still missing two more steps. First, we did not assign the list’s head pointer. Second, the last element’s right pointer does not point to the first element (similar to the first element’s left pointer).
// Just update the current node’s right pointer to point back to the head and the head’s left pointer to point to current node in each recursive call.
// As the recursion ends, the list’s head and tail would be automagically updated with the correct pointers.
// Don’t forget to check for this special case: A list with only one element should have its left and right pointers both pointing back to itself.

Solution 1: recursion
O(n) time, O(h) space

TreeNode head = null, prev = null;
public TreeNode convertBSTtoCircularDL(TreeNode root) {
convert(root);
}
public void convert(TreeNode root) {
if (root == null)    return;
convert(root.left);
root.left = prev;
if (prev != null)    prev.right = root;
else    head = root;
// would make head <-> tail in the end
TreeNode right = root.right;
prev = root;
convert(right);
}

Solution 2: iteration
O(n) time, O(h) space

public TreeNode bstToDoublyList(TreeNode root) {
TreeNode head = null, prev = null;
Stack<TreeNode> stack = new Stack<>();
while (root != null || !stack.empty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
root.left = prev;
if (prev != null)    prev.right = root;
else     head = root;
TreeNode right = root.right;
root.right = head;//remember to update the prev !!!
prev = root;
root = right;//we should root=root.right even if it's null!!!
}
}
``````

Followup: Reverse Operation:

`````` private static BSTNode DLtoBST(BSTNode head){
// unlink the tail
BSTNode tail = head.left;
tail.right = null;

}
private static BSTNode toBST(BSTNode head, BSTNode tail){
if (head == tail) return null;
BSTNode fast = head, slow = head;
while(fast != tail && fast.right != tail){
fast = fast.right.right;
slow = slow.right;
}

// slow is the root of the tree
slow.left = toBST(head, slow);
slow.right = toBST(slow.right, tail);

return slow;
}
``````