# BST To DLL

## Question ([LI.378](http://www.lintcode.com/en/problem/convert-binary-search-tree-to-doubly-linked-list/))

> Convert a binary search tree to a sorted doubly linked list in place.

Node definition? node.left is prev and node.right is next.

## Example

```
I:
    4
   / \
  2   5
 / \
1   3

O: 1<->2<->3<->4<->5
```

## Analysis

In order traversal will print the nodes in a sorted order. Linking up the final node and the first node then it will be circular. In place is the hard part because we need to modify the tree structure.

## Code

Iterative in-order traversal is one approach. The treenode is saved in stack so modifying will not lose the link.