BST To DLL

Question (LI.378)

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.