Convert Sorted Doubly Linked List to Balanced BST (In-Place)

Problem Statement

Given a sorted Doubly Linked List, convert it into a height-balanced Binary Search Tree (BST).

Constraint: You must NOT create new nodes. Reuse the existing DLL nodes — the prev pointer becomes left child and next pointer becomes right child.

Constraints

• 1 <= number of nodes <= 10^5
• DLL is sorted in ascending order
• No new nodes allowed — rearrange pointers only
• Result must be height-balanced (height difference between subtrees ≤ 1)

Example

Input DLL: 1 ↔ 2 ↔ 3 ↔ 4 ↔ 5 ↔ 6 ↔ 7

Output BST:

        4
       / \
      2    6
     / \  / \
    1   3 5   7

Where left = prev pointer, right = next pointer.

What the Interviewer Expects

1. Find the middle node — this becomes the root (ensures balance).
2. Recursively build left and right subtrees — left half of DLL becomes left subtree, right half becomes right subtree.
3. Two approaches:
   • Top-down: find middle each time (O(n log n))
   • Bottom-up: advance a pointer as you build (O(n)) — similar to sortedListToBST on LeetCode
4. Pointer reassignment — node.prev = leftChild, node.next = rightChild. Break DLL links properly.
5. Height-balanced proof — always picking the middle guarantees balance.

Follow-ups

1. Can you do this in O(n) time? (Bottom-up approach without finding middle repeatedly)
2. What if the DLL is circular? How do you determine length/start?
3. What if the linked list is singly linked? What changes?
4. How would you verify the output is a valid BST AND height-balanced?