Convert Sorted List to Binary Search Tree
Last Updated: April 1, 2026
Understanding the Problem
We're given a sorted singly linked list and need to build a height-balanced BST from it. This is closely related to converting a sorted array to a BST, but the linked list twist changes things. With an array, we can jump to the middle element in O(1). With a linked list, finding the middle requires traversal.
The sorted order of the list is the in-order traversal of the BST we want to build. To keep the tree balanced, we want the middle element as the root, with roughly equal numbers of nodes on each side. The core challenge is efficiently finding the middle of a linked list (or avoiding the need to find it at all).
Key Constraints:
0 <= n <= 2 * 10^4→ With up to 20,000 nodes, O(n^2) is fine but O(n log n) or O(n) would be better. The list can be empty, so we need to handle that.-10^5 <= Node.val <= 10^5→ Standard integer range, no overflow concerns.- Elements are sorted in ascending order → The list is an in-order traversal. No duplicates are implied by BST structure.
Approach 1: Convert to Array, Then Divide and Conquer
Intuition
The most straightforward approach: sidestep the linked list limitation entirely. Copy all values into an array, then solve the familiar problem of converting a sorted array to a height-balanced BST by picking the middle element as root and recursing on both halves.
This works because the only hard part of this problem is that linked lists don't support random access. An array does. So if we can afford the extra O(n) space, we can reduce this to a problem we already know how to solve.
Algorithm
- Traverse the linked list and copy all values into an array.
- Use divide and conquer on the array: pick the middle element as root.
- Recursively build the left subtree from the left half of the array.
- Recursively build the right subtree from the right half of the array.
- Return the root.
Example Walkthrough
Input:
After copying to array and applying divide and conquer (pick middle as root, recurse on halves):
Resulting BST:
Code
- Time Complexity: O(n). We traverse the list once to copy values and visit each element once during divide and conquer.
- Space Complexity: O(n). The array storing all values takes O(n) space. The recursion stack is O(log n).
This approach works correctly but uses O(n) extra space to duplicate the input data. Can we build the BST directly from the linked list without the extra array?
Approach 2: Slow/Fast Pointer to Find Middle
Intuition
Instead of copying everything into an array, we can work with the linked list directly. The key technique is using slow and fast pointers to find the middle of a linked list. The slow pointer moves one step at a time while the fast pointer moves two steps. When the fast pointer reaches the end, the slow pointer is at the middle.
Once we find the middle node, it becomes the root of the current subtree. Everything before it forms the left subtree, and everything after it forms the right subtree. We disconnect the left half by setting the previous node's next pointer to null, then recurse on both halves.
The slow/fast pointer technique guarantees we find the middle of any linked list segment. By always choosing the middle as the root and recursing on both halves, we build a balanced tree structure. The BST property holds because the list is sorted: everything before the middle is smaller, everything after is larger.
Algorithm
- Base case: if the list is empty, return null.
- Use slow/fast pointers to find the middle node. Also track the node just before the middle.
- Disconnect the left half by setting
prev.next = null. - Create a tree node with the middle node's value.
- Recursively build the left subtree from the head of the left half.
- Recursively build the right subtree from the node after the middle.
- Return the current node.
Example Walkthrough
Code
- Time Complexity: O(n log n). At each level of recursion, we traverse all n nodes total to find midpoints. There are O(log n) levels.
- Space Complexity: O(log n). The recursion stack goes O(log n) deep for a balanced tree. No auxiliary data structures are used.
This eliminates the extra array, but finding the middle at every recursion level is redundant work. Since the list is in sorted (in-order) order, can we build the tree by reading nodes left to right without ever searching for the middle?
Approach 3: In-Order Simulation (Optimal)
Intuition
Here's the key insight: the sorted linked list is the in-order traversal of the BST we want to build. If we simulate this traversal, we can build the tree by reading nodes from the linked list one by one in order.
We know the total size of the list (count it once at the start). We then recursively build the tree by size ranges. When we recurse to build the left subtree of size k, those k recursive calls "consume" the first k nodes from the linked list. After the left subtree is built, the linked list pointer is sitting at exactly the node that should be the current root. We create the root node, advance the pointer, then build the right subtree.
The beauty of this approach is that we never need to find the middle. The recursion structure and the linked list pointer work together to naturally assign each node to its correct position in the tree. Each node is visited exactly once, giving us O(n) time.
In-order traversal of a BST visits nodes in sorted order. Since our linked list is already in sorted order, we can think of the list as the "script" for an in-order traversal. By building the left subtree first (which consumes the smallest nodes), then the root (the next node in sorted order), then the right subtree (which consumes the remaining larger nodes), we guarantee that each node ends up in exactly the right position.
Algorithm
- Count the total number of nodes in the linked list.
- Maintain a pointer (class variable) to the current position in the linked list.
- Define a recursive function
build(left, right)where left and right represent index bounds. - If
left > right, return null (base case). - Find the midpoint:
mid = left + (right - left) / 2. - Recursively build the left subtree with
build(left, mid - 1). This advances the list pointer. - Create the current node from the value at the current list pointer. Advance the pointer.
- Recursively build the right subtree with
build(mid + 1, right). - Return the current node.
Example Walkthrough
Code
- Time Complexity: O(n). We traverse the list once to count nodes, then each node is consumed exactly once during the recursive build.
- Space Complexity: O(log n). The recursion stack depth equals the height of the balanced tree. No auxiliary data structures are used.