Problem

Given a sorted doubly linked list, convert it into a balanced binary search tree (BST) in place, such that the tree maintains the properties of the BST and the elements of the tree’s in-order traversal match the elements’ order in the linked list.

Examples

Example 1:

1
2
3
4
5
6
7
8

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:

1
2
3
4
5
6
7
8

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:

1
2
3
4
5
6
7
8

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

  • To convert a sorted doubly linked list to a BST, we can use the in-order properties of BST (left, root, right).
  • We can recursively build the tree by dividing the linked list into two halves - left half becomes the left subtree, middle becomes the root, and right half becomes the right subtree.
  • In each recursive call, we need to efficiently find the middle of the linked list to keep the tree balanced.

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 elements before and after the middle element respectively.
  3. Use a helper function to find the middle of the linked list and adjust the pointers accordingly without creating new nodes.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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

    private TreeNode sortedListToBSTHelper(DLLNode start, DLLNode end) {
        if (start == end) return null;
        
        DLLNode mid = getMiddle(start, end);
        TreeNode node = new TreeNode(mid.val);
        node.left = sortedListToBSTHelper(start, mid);
        node.right = sortedListToBSTHelper(mid.next, end);
        
        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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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 = self.TreeNode(mid.val)
        node.left = self.sortedListToBSTHelper(start, mid)
        node.right = self.sortedListToBSTHelper(mid.next, end)
        
        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.