Problem

Given a sorted doubly linked list, convert it into a balanced binary search tree (BST) in place such that:

  • The prev pointer serves as the left child.
  • The next pointer serves as the right child.
  • The transformation happens in-place.

Examples

Example 1:

Input: DLL: 1 <-> 2 <-> 3 <-> 4 <-> 5 
Output: BST: 
          3
         / \
        2   5
       /   /
      1   4
Explanation: The doubly linked list 1 <-> 2 <-> 3 <-> 4 <-> 5 is converted to a balanced BST.

Example 2:

Input: DLL: 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 6 <-> 7
Output: BST: 
           4
         /   \
        2     6
       / \   / \
      1   3 5   7
Explanation: The doubly linked list 1 <-> 2 <-> 3 <-> 4 <-> 5 is converted to a balanced BST.

Example 3:

Input: DLL: -10 <-> -3 <-> 0 <-> 5 <-> 9
Output: BST: 
          0
         / \
       -3   9
       /   /
     -10  5
Explanation: The doubly linked list -10 <-> -3 <-> 0 <-> 5 <-> 9 is converted to a balanced BST.

Solution

Method 1 - Recursion

  • We use the same approach to find the middle element of the doubly linked list.
  • The middle element becomes the root, prev becomes left, and next becomes right.
  • Perform this recursively to build the tree in-place.

Approach

  1. Find the middle element of the doubly linked list to serve as the root of the BST.
  2. Recursively construct the left and right subtrees using the prev and next pointers.
  3. Use a helper function to recursively divide the linked list and adjust pointers in place without creating new nodes.

Code

Java
class Solution {
    public DLLNode sortedListToBST(DLLNode head) {
        if (head == null) return null;
        return sortedListToBSTHelper(head, null);
    }

    private DLLNode sortedListToBSTHelper(DLLNode start, DLLNode end) {
        if (start == end) return null;
        
        DLLNode mid = getMiddle(start, end);
        DLLNode node = mid;  // Node itself
        
        node.prev = sortedListToBSTHelper(start, mid); // Assign left child
        node.next = sortedListToBSTHelper(mid.next, end); // Assign right child
        
        return node;
    }
    
    private DLLNode getMiddle(DLLNode start, DLLNode end) {
        DLLNode slow = start;
        DLLNode fast = start;
        
        while (fast != end && fast.next != end) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        return slow;
    }
}
Python
class Solution:
    def sortedListToBST(self, head):
        if not head:
            return None
        return self.sortedListToBSTHelper(head, None)

    def sortedListToBSTHelper(self, start, end):
        if start == end:
            return None
        
        mid = self.getMiddle(start, end)
        node = mid  # Node itself
        
        node.prev = self.sortedListToBSTHelper(start, mid)  # Assign left child
        node.next = self.sortedListToBSTHelper(mid.next, end)  # Assign right child
        
        return node

    def getMiddle(self, start, end):
        slow, fast = start, start
        while fast != end and fast.next != end:
            slow = slow.next
            fast = fast.next.next
        return slow

Complexity

  • ⏰ Time complexity: O(n) where n is the number of nodes in the doubly linked list.
  • 🧺 Space complexity: O(log n) due to recursion stack used when dividing the list.