# Binary Search Tree to sorted doubly-linked list

**Problem statement**

Given the root of a Binary Search Tree (BST), convert the BST to a sorted doubly linked list in-place. BST is formed only on `left`

and `right`

pointers. `prev`

and `next`

pointers are unassigned initially. Initialise `prev`

and `next`

pointers of `Node`

for creating a doubly-linked list. BST and doubly-linked list should co-exist in the same structure. The abstract structure of `Node`

is given as follows:

1 2 3 4 5 6 |
Node -> left, right, prev, next, value |

**Solution**

We will solve this problem using in-order tree traversal. The way in-order tree traversal works, is as follows: the left subtree is visited first, then the root and later the right sub-tree.

1 2 3 |
Step 1 − Recursively traverse left subtree. Step 2 − Visit root node. Step 3 − Recursively traverse right subtree. |

Obviously if a BST is traversed in-order, the output will produce sorted values in an ascending order.

Since we want a doubly-linked list as our result we will need to keep track of the first element in the list, `head`

. We also need to keep track of the previously visited element, `prev`

, so that we can set it as the current node’s previous node.

Initially, both `head`

and `prev`

are set to `null`

. We then traverse the left subtree all the way down. When there is no more left subtree left to traverse we know we have reached the smallest element. This element is going to be our `head`

(first element in the list). We set the current node’s previous link to point to `prev`

(Note: for `head`

previous will point to `null`

). We also set the `prev`

(if `prev`

is not equal to `null`

) node’s next to point to the current node. Then, before we continue with the right subtree we set `prev`

to the current node. We then recursively call the in-order function for the right subtree.

The full code is listed below.

**Full code**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 |
public class BSTToDoublyLinkedList { static class BST<T extends Comparable<T>> { private T data; private BST<T> left = null; private BST<T> right = null; private BST<T> next = null; private BST<T> prev = null; public BST(T data) { this.data = data; } public BST<T> addNode(T newData) { BST<T> result; if (newData.compareTo(this.data) <= 0) { // Go left if (left == null) { left = new BST<T>(newData); result = left; } else { result = left.addNode(newData); } } else { // Go right if (right == null) { right = new BST<T>(newData); result = right; } else { result = right.addNode(newData); } } return result; } public String toString() { StringBuilder result = new StringBuilder("["); result.append(this.data.toString()); if (left != null || right != null) { result.append("->"); if (left != null) { result.append(left.toString()); } if (right != null) { result.append(right.toString()); } } result.append("]"); return result.toString(); } } static BST<Integer> prev = null; static BST<Integer> head = null; private static void inorderTraversal(BST<Integer> node) { if (node == null) { return; } inorderTraversal(node.left); node.prev = prev; if (prev != null) { prev.next = node; } else { head = node; } // Uncomment for circled linked list // head.prev = node; // node.next = head; prev = node; inorderTraversal(node.right); } public static void main(String[] args) { BST<Integer> root = new BST<Integer>(5); root.addNode(1); root.addNode(10); root.addNode(8); root.addNode(2); inorderTraversal(root); // Print Tree System.out.println(root); // Print List while (head != null) { System.out.print(head.data + " "); head = head.next; } } } |