## [f]izzbuzzer

### Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

# Binary Search Tree to sorted doubly-linked list

Sharing is caring!

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:

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

```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

```public class BSTToDoublyLinkedList {
static class BST> {
private T data;
private BST left = null;
private BST right = null;

private BST next = null;
private BST prev = null;

public BST(T data) {
this.data = data;
}

BST result;

if (newData.compareTo(this.data) <= 0) {
// Go left
if (left == null) {
left = new BST(newData);
result = left;
} else {
}
} else {
// Go right
if (right == null) {
right = new BST(newData);
result = right;
} else {
}
}

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 prev = null;

private static void inorderTraversal(BST node) {
if (node == null) {
return;
}

inorderTraversal(node.left);

node.prev = prev;
if (prev != null) {
prev.next = node;
} else {
}

// Uncomment for circled linked list

prev = node;

inorderTraversal(node.right);
}

public static void main(String[] args) {
BST root = new BST(5);

inorderTraversal(root);

// Print Tree
System.out.println(root);

// Print List