Convert a Sorted Doubly Linked List to a Balanced BST In Place
Company: Salesforce
Role: Member of Technical Staff
Category: Software Engineering Fundamentals
Difficulty: medium
Interview Round: Onsite
# Convert a Sorted Doubly Linked List to a Balanced BST In Place
You are given the head of a sorted doubly linked list. Each node has `prev`, `next`, and `value` fields. Rewire the existing nodes into a height-balanced binary search tree without allocating any new node.
In the resulting tree, interpret `prev` as the left-child pointer and `next` as the right-child pointer. Return the root. Preserve every input node exactly once, and preserve the list's nondecreasing in-order value sequence.
### Constraints & Assumptions
- The input list may be empty and may contain duplicate values.
- `prev` and `next` are the only structural pointers available on a node.
- Auxiliary scalar state and call-stack space are allowed; allocating replacement tree nodes or arrays of nodes is not.
- Height-balanced means the left and right subtree heights of every node differ by at most one.
### Clarifying Questions to Ask
- May duplicate values appear, and is preserving their original in-order identity sufficient?
- Does “in place” permit recursion-stack memory?
- Must the input list remain traversable after conversion, or may all links be repurposed?
- How should an empty list be returned?
### What a Strong Answer Covers
- Counting the list length without losing the head or corrupting links.
- Building the tree in in-order sequence so the sorted list supplies nodes without repeated midpoint scans.
- Reusing one current-list pointer and assigning each consumed node's `prev` and `next` as tree children.
- Correct subtree sizes for even and odd lengths and a clear duplicate-value invariant.
- `O(n)` time, logarithmic recursion depth for the balanced construction, and no new node allocation.
- Edge cases for empty, singleton, two-node, and already skewed pointer layouts.
### Follow-up Questions
1. Why does repeatedly walking to the middle of each sublist become slower than linear time?
2. At what point may the algorithm safely overwrite the current node's original `prev` and `next` links?
3. How do subtree sizes guarantee the resulting height bound?
4. What would change if even recursion-stack allocation were prohibited?
Overview: Rewire a sorted doubly linked list into a height-balanced binary search tree without allocating replacement nodes. The solution uses list length and in-order construction to preserve node identity, duplicates, linear time, balanced subtree sizes, and safe pointer updates.
Read the full Salesforce Member of Technical Staff interview experience this question came from