AlgoMaster Logo

Convert Sorted List to Binary Search Tree

mediumFrequency7 min readUpdated June 23, 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, with one difference that drives the whole problem: an array can jump to its middle element in O(1), while a linked list has to walk there node by node.

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 → O(n log n) and even O(n^2) pass within this bound, but an O(n) solution exists. The list can be empty, so the code must handle a null head.
  • -10^5 <= Node.val <= 10^5 → Values fit comfortably in a 32-bit integer, no overflow concerns.
  • Elements are sorted in ascending order → The list is the in-order traversal of the tree we need to build. Approach 3 relies on this directly.

Approach 1: Convert to Array, Then Divide and Conquer

Intuition

Copy all values into an array first, then solve the array version of the problem: pick the middle element as the root and recurse on both halves. The only obstacle in this problem is that a linked list lacks random access, and an array restores it. The cost is O(n) extra space to duplicate the input.

Algorithm

  1. Traverse the linked list and copy all values into an array.
  2. Use divide and conquer on the array: pick the middle element as root.
  3. Recursively build the left subtree from the left half of the array.
  4. Recursively build the right subtree from the right half of the array.
  5. Return the root.

Example Walkthrough

Input:

-10
-3
0
5
9
null
head

Copying the list produces this array:

0
-10
1
-3
2
0
3
5
4
9
values

The recursion runs as follows:

  1. build(0, 4): mid = 2, so 0 becomes the root. Recurse on indices 0 to 1 and 3 to 4.
  2. build(0, 1): mid = 0, so -10 becomes the root's left child. build(0, -1) returns null, and build(1, 1) makes -3 the right child of -10.
  3. build(3, 4): mid = 3, so 5 becomes the root's right child. build(3, 2) returns null, and build(4, 4) makes 9 the right child of 5.

Resulting BST:

0-10-359
BST

Code

The array doubles the memory footprint of the input. The next approach drops it and works on the linked list in place.

Approach 2: Slow/Fast Pointer to Find Middle

Intuition

Instead of copying everything into an array, we can work with the linked list directly. Slow and fast pointers find the middle of a list: the slow pointer moves one step for every two steps the fast pointer takes, so when fast reaches the end, slow is at the middle.

The middle node becomes the root of the current subtree. Everything before it is smaller (the list is sorted) and forms the left subtree; everything after it is larger and forms the right subtree, so the BST property holds at every node. The split also keeps the two halves within one node of each other in size, which is what makes the result height-balanced. We disconnect the left half by setting the previous node's next pointer to null, then recurse on both halves.

The single-node base case below is required for termination. With one node, the slow pointer never moves, prev stays null, nothing gets disconnected, and the left recursion would receive the same one-node list again and loop forever.

Algorithm

  1. Base cases: if the list is empty, return null. If it has a single node, return a leaf with that value.
  2. Use slow/fast pointers to find the middle node. Also track the node just before the middle.
  3. Disconnect the left half by setting prev.next = null.
  4. Create a tree node with the middle node's value.
  5. Recursively build the left subtree from the head of the left half.
  6. Recursively build the right subtree from the node after the middle.
  7. Return the current node.

Example Walkthrough

1Initial list: find middle using slow/fast pointers
slow
-10
fast
-3
0
5
9
null
1/7

Code

This eliminates the extra array, but every recursion level re-scans its segment to find the middle, which is where the extra log n factor comes from. The list is already in in-order sequence, and the final approach uses that to read each node exactly once.

Approach 3: In-Order Simulation (Optimal)

Intuition

An in-order traversal of a BST visits nodes in sorted order, and our list is already sorted. So instead of searching for each subtree's root, we can run an in-order traversal that creates nodes instead of reading them: visit the positions of the balanced tree in in-order sequence and hand each one the next value from the list.

Count the total size of the list once, then recurse over index ranges, exactly as in the array version. The difference is that no call ever indexes into anything. When a call builds its left subtree over k indices, those k node creations consume the first k nodes from the list. Once the left subtree is finished, the shared list pointer sits at exactly the node that belongs at the current root. Create the root from it, advance the pointer, then build the right subtree from the remaining indices.

The midpoint computation still appears, but it only decides how many indices go to each side (which is what keeps the tree balanced). The values come from the list pointer, which moves forward one node per created tree node. Each node is read once, giving O(n) time.

Algorithm

  1. Count the total number of nodes in the linked list.
  2. Maintain a shared pointer (class member or closure variable) to the current position in the linked list, starting at the head.
  3. Define a recursive function build(left, right) where left and right are index bounds.
  4. If left > right, return null (base case).
  5. Compute the midpoint: mid = left + (right - left) / 2. This splits the index range; it is never used to read a value.
  6. Recursively build the left subtree with build(left, mid - 1). This advances the list pointer past the left subtree's nodes.
  7. Create the current node from the value at the list pointer, then advance the pointer.
  8. Recursively build the right subtree with build(mid + 1, right).
  9. Return the current node.

Example Walkthrough

1Start: current at head. build(0,4): mid=2, recurse left into build(0,1)
-10
current
-3
0
5
9
null
1/7

Code