Convert Sorted List to Binary Search Tree

A sorted array gives you the middle value immediately. A singly linked list makes you walk for it. The better solution avoids the walk entirely: let recursion choose the shape, and let the list supply values in inorder.

The contract and the key constraint

You receive the head of a singly linked list whose values are sorted in ascending order. Return a height-balanced binary search tree containing every list value exactly once. An empty list returns an empty tree.

“Height-balanced” means that, at every node, the heights of the left and right subtrees differ by at most one. That is stronger than merely returning a valid BST. A chain such as

1
 \
  2
   \
    3

respects ascending order, but it is not balanced.

The solution has two obligations:

1. Preserve the list's sorted order in the tree.
2. Divide the values into nearly equal left and right subtrees.

The first obligation comes from the BST invariant: an inorder traversal visits values from left to root to right. The second requires choosing a middle position for each subtree.

That creates the central constraint. With a sorted array, you can read values[mid] in constant time. With a singly linked list, there is no index lookup. Reaching the middle means walking from the head.

The obvious array-style recursion therefore does not transfer directly.

Recognize the inorder construction pattern

The key reframe is simple:

The linked list is the inorder stream. Recursion decides the tree shape.

Suppose the list contains five values:

-10 -> -3 -> 0 -> 5 -> 9

The balanced tree should use the middle position as its root. Its inorder traversal must still produce:

-10, -3, 0, 5, 9

Instead of asking the list for its middle node, build the tree in the same order that inorder traversal would visit it:

1. Build the left subtree.
2. Use the next list value as the current root.
3. Build the right subtree.

The recursive call determines how many nodes belong to the left subtree. Once those nodes have been built, the next list node must be the root. The remaining nodes belong to the right subtree.

This is a depth-first construction. We descend into the left subtree, return to create the current node, then descend into the right subtree. The recursion is doing two jobs at once:

• Index ranges determine the shape and size of each subtree.
• A shared linked-list pointer supplies values in sorted order.

The midpoint is still useful, but only as a structural boundary. We calculate it from integer indices; we never use it to index into the linked list.

Baseline approaches and the real tradeoff

There are two reasonable approaches to consider before choosing the optimized version.

Copy the list into an array

First, walk through the list and store its values in a Python list. Then solve the familiar sorted-array problem:

build(left, right):
    choose mid
    make values[mid] the root
    build the left range
    build the right range

This takes O(n) time to copy the values and O(n) extra space for the array. The tree construction itself also takes O(n) time.

This is a legitimate interview solution. It is easy to explain, easy to debug, and often the best first implementation if the problem does not care about auxiliary memory.

Find each linked-list midpoint

Another option is to use slow and fast pointers to find the middle node of each current sublist. Then recursively build the two halves, usually by cutting the list around the midpoint.

This avoids the value array, but it introduces repeated scanning. Finding the midpoint at each recursion level costs linear work across that level, producing O(n log n) time for balanced splits. It also makes the implementation responsible for rewiring list links correctly.

The preferred solution counts the nodes once and then consumes each list node exactly once during construction. That gives:

• O(n) time
• O(log n) recursion stack space, excluding the output tree
• no O(n) array of copied values

My interview rule is practical: use the array version when clarity and extra memory are acceptable. Use the shared-pointer version when the linked-list representation is central and you want the linear-time solution.

Derive the recursive state and invariant

First count the number of list nodes, n. This gives us an abstract index range:

[0, n - 1]

The indices do not refer to positions we can access in the linked list. They represent inorder positions and tell us how many nodes each recursive call must create.

Define:

build(left, right)

This helper builds the balanced subtree whose inorder positions lie between left and right, inclusive.

The base case is:

left > right

That range contains no nodes, so the helper returns None.

For a nonempty range:

mid = (left + right) // 2

Then perform the operations in this exact order:

1. Build the left range [left, mid - 1].
2. Read the current linked-list node as the root value.
3. Advance the linked-list pointer once.
4. Build the right range [mid + 1, right].
5. Return the root.

The order is the algorithm. Move the pointer at the wrong time and the tree receives the wrong values.

The central invariant is:

Before build(left, right), the shared list pointer references the first value belonging to that inorder range. After the call, exactly those values have been consumed, and the returned subtree is balanced and ordered.

Why does building the left subtree advance the pointer to the correct root? Because the left subtree consumes exactly as many values as its range contains. The next value in the sorted stream is therefore the value at inorder position mid.

The list pointer must be consumed between the left and right recursive calls. If you read the pointer first, the first list value becomes the root even when the subtree has values that should appear before it. That breaks inorder assignment.

Prove correctness instead of trusting the trace

A short induction argument covers the important properties.

Base case

When left > right, the range is empty. The helper returns None, consumes no list node, and constructs an empty subtree. The invariant holds.

Inductive step

Assume the helper works correctly for smaller ranges.

For a nonempty range [left, right], choose mid.

The left recursive call handles [left, mid - 1]. By the induction assumption, it constructs a balanced left subtree and consumes exactly the values assigned to the earlier inorder positions.

The shared pointer now references the next value in sorted order. That value becomes the current root, and the pointer advances exactly once.

The right recursive call handles [mid + 1, right]. By the induction assumption, it constructs a balanced right subtree from the remaining values.

Because the input is sorted, the values consumed by the left subtree come before the root value, and the values consumed by the right subtree come after it. Therefore, the returned tree has the required inorder ordering.

No value is skipped or reused:

• Every nonempty range creates exactly one tree node.
• Creating that node advances the list pointer exactly once.
• The recursive ranges partition the original range into left, root, and right positions.

Balance follows from the midpoint split. The left and right ranges contain subtree node counts that differ by at most one. The same property holds recursively at every node, so the resulting tree is height-balanced.

If the input contract allows duplicate values, preserve the contract's ordering convention. The construction guarantees sorted inorder consumption; do not add a strict < or > claim unless the problem explicitly requires distinct values.

Dry-run the pointer and subtree sizes

Use the list:

-10 -> -3 -> 0 -> 5 -> 9

There are five nodes, so the initial range is [0, 4].

The resulting shape is:

        0
      /   \
   -10     5
      \     \
      -3     9

The first list value, -10, is not the root. It becomes the leftmost node because the recursion must finish the left subtree before consuming the root value for the [0, 4] range.

Check the result in the direction the algorithm was designed:

inorder(tree) == [-10, -3, 0, 5, 9]

That check exposes the common mental error. The list is not being split by repeatedly walking to its middle. It is being consumed as the tree's inorder output.

Convert Sorted List to Binary Search Tree Python solution

The Python implementation uses:

• One pass to count the nodes.
• current as the shared pointer into the linked list.
• build(left, right) to control subtree sizes.
• nonlocal current so recursive calls update the same pointer.

The platform supplies ListNode and TreeNode, so the solution only implements the conversion method.

class Solution:
    def sortedListToBST(self, head):
        # Count the nodes so recursion can work with index ranges.
        n = 0
        node = head

        while node is not None:
            n += 1
            node = node.next

        current = head

        def build(left, right):
            nonlocal current

            # No inorder positions remain in this subtree.
            if left > right:
                return None

            mid = left + (right - left) // 2

            # Build earlier inorder positions first.
            left_child = build(left, mid - 1)

            # The next list value is the root at inorder position mid.
            root = TreeNode(current.val)
            current = current.next

            # Build later inorder positions.
            right_child = build(mid + 1, right)

            root.left = left_child
            root.right = right_child
            return root

        return build(0, n - 1)

The code may look unusual if you expect the root to be created before its children. That is normal for this construction. The list values arrive in inorder order, so the left subtree must consume its values first.

The line that advances current is especially important:

current = current.next

It executes once for every created tree node. It does not happen before the left recursion, and it does not happen more than once.

The midpoint calculation also deserves attention:

mid = left + (right - left) // 2

It divides the abstract range. It does not attempt to access the linked list at position mid.

Complexity, edge cases, and failure modes

Let n be the number of list nodes.

Time complexity

The counting pass visits each list node once: O(n).

The recursive construction creates one tree node per list node and performs constant work around each recursive call: O(n).

Together, the total time is:

O(n)

Space complexity

The returned tree contains n nodes, so the output itself uses O(n) space.

The recursion follows a balanced tree, so its maximum call-stack depth is O(log n). The shared pointer avoids storing a second copy of all values.

Therefore:

• Auxiliary recursion space: O(log n)
• Output space: O(n)

Keep those categories separate. Saying simply “space is O(n)” hides the fact that the algorithm does not allocate an extra array.

Edge cases

Test these before trusting a larger example:

• Empty list: n = 0, so build(0, -1) returns None.
• One node: the node becomes a leaf.
• Two nodes: one becomes the root and the other becomes a child. Either consistent midpoint choice can remain height-balanced.
• Five nodes: the root receives the third inorder value, while the two remaining ranges build the subtrees.
• Sorted input with duplicates: follow the ordering convention specified by the problem. Do not assume a strict inequality rule that the contract does not state.

Common failure modes

Using list indexing.
A linked list does not support constant-time access by position. If the helper tries to retrieve the middle node by walking from the head in every call, it loses the linear-time advantage.

Advancing the pointer before the left subtree.
This assigns the wrong value to the root and shifts every later assignment.

Forgetting to advance the pointer.
Every recursive call then reuses the same list value, producing a tree with repeated values.

Mixing range conventions.
This article uses inclusive ranges [left, right]. The empty condition is left > right, and the child ranges are mid - 1 and mid + 1. Half-open ranges can work too, but do not mix the two styles.

Reusing linked-list nodes as tree nodes.
A list node has a next pointer; a tree node needs left and right pointers. Create new TreeNode objects for the result.

Expecting one unique shape.
The requirement is a height-balanced BST containing the values. Different midpoint conventions can produce different valid shapes, especially for even-sized ranges.

The transferable recognition rule

When a sorted linked sequence must become a balanced BST, do not fight the list by repeatedly searching for its middle.

Treat the sequence as an inorder stream:

1. Count the values.
2. Let subtree sizes determine the shape.
3. Build the left subtree.
4. Consume one list value as the root.
5. Build the right subtree.

Write that invariant before writing code. Then test the pointer position and inorder output on an empty list, a one-node list, and the five-node example.

The list supplies order. DFS supplies structure.