Convert Binary Search Tree to Sorted Doubly Linked List

Convert Binary Search Tree to Sorted Doubly Linked List

What is this problem about?

The Convert Binary Search Tree to Sorted Doubly Linked List interview question tasks you with transforming a BST into a circular doubly linked list in-place. The nodes in the list should be in sorted order (based on their values in the tree), and the left and right pointers of the tree nodes should be repurposed as prev and next pointers for the list.

Why is this asked in interviews?

Companies like Meta and Google ask the Convert Binary Search Tree to Sorted Doubly Linked List coding problem to test a candidate's ability to manipulate complex pointer relationships. It requires a deep understanding of In-order Traversal and the ability to maintain state (like the "previous" node visited) across recursive calls.

Algorithmic pattern used

This follows the Binary Search Tree, Depth-First Search, Doubly-Linked List interview pattern.

1. Perform an in-order DFS.
2. Maintain a first node (to store the head of the list) and a last node (to track the most recently processed node).
3. At each node in the traversal:
   • Link last.right = current and current.left = last.
   • Update last = current.
4. After the traversal, link last.right = first and first.left = last to make it circular.

Example explanation

BST:

    4
   / 
  2   5
 / 
1   3

1. In-order starts: 1. first = 1, last = 1.
2. Next: 2. Link 1 and 2. last = 2.
3. Next: 3. Link 2 and 3. last = 3.
4. Next: 4. Link 3 and 4. last = 4.
5. Next: 5. Link 4 and 5. last = 5.
6. End: Link 5 back to 1. Result: 1 <-> 2 <-> 3 <-> 4 <-> 5 (<-> 1).

Common mistakes candidates make

• Not in-place: Creating new list nodes instead of reusing the tree nodes.
• Forgetting Circularity: Connecting the nodes in a line but failing to connect the head and tail.
• Null head: Not handling the case where the tree is empty.

Interview preparation tip

In-place tree transformations are all about pointer re-assignment. Draw out the tree and the desired list, and trace how the left and right pointers change at each step of the in-order traversal.