> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-1/basic_data_structure/linked_list/doubly-linked-list/bst-to-dll.md).

# 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.