Hoarding programming problems for you!

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:

Sample input

Sample output

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.

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