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
Binary Search Tree (BST) to sorted doubly-linked list

Sample output
Binary Search Tree (BST) to sorted doubly-linked list

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