Convert Sorted List to BST: Finding the Middle with Slow/Fast Pointers

Convert Sorted List to Binary Search Tree is LeetCode problem 109. It combines two fundamental ideas: finding the middle of a linked list with slow/fast pointers, and recursively building a tree from sorted data. If you have solved the array version of this problem, the linked list version adds one twist: you cannot index into the middle in O(1), so you need the slow/fast pointer technique to find it.

The problem

Given the head of a singly linked list where elements are sorted in ascending order, convert it to a height-balanced binary search tree. A height-balanced BST is one where the depth of the two subtrees of every node never differs by more than 1.

Example: head = [-10, -3, 0, 5, 9] produces the BST [0, -3, 9, -10, null, 5].

The approach

The key insight is that the middle element of a sorted sequence should be the root. That gives you equal (or near-equal) elements on each side, which is exactly what a height-balanced BST needs.

For an array, you grab the middle index directly. For a linked list, you find the middle node using the slow/fast pointer technique:

1. Find the middle node with slow/fast pointers. slow moves one step, fast moves two. When fast reaches the end, slow is at the middle.
2. Make the middle node the root of the BST.
3. Recurse on the left half (everything before the middle) to build the left subtree.
4. Recurse on the right half (everything after the middle) to build the right subtree.

Each recursive call repeats the same process: find the middle, make it a node, split, recurse. Base case: if the list is empty (head is null), return null. If there is only one node, return it as a leaf.

Visual walkthrough

Trace through the list [-10, -3, 0, 5, 9]. Watch the slow/fast pointers find the middle, then see the tree build up recursively.

Each level of recursion halves the list. The slow/fast scan takes O(n) at the top level, O(n/2) at the next, and so on. The tree grows from the root outward, with every middle node becoming the parent of its subtrees.

The solution

def sortedListToBST(head):
    if not head:
        return None
    if not head.next:
        return TreeNode(head.val)

    prev = None
    slow = head
    fast = head

    while fast and fast.next:
        prev = slow
        slow = slow.next
        fast = fast.next.next

    if prev:
        prev.next = None

    root = TreeNode(slow.val)
    root.left = sortedListToBST(head)
    root.right = sortedListToBST(slow.next)

    return root

Here is what each part does:

1. Base cases. If head is null, return null. If there is only one node, return it as a leaf.
2. Slow/fast scan. prev tracks the node before slow so you can cut the list. When fast reaches the end, slow is at the middle.
3. Cut the list. Set prev.next = None to split the left half from the middle. Now head leads a sublist that ends before slow.
4. Build the root. Create a TreeNode with slow.val.
5. Recurse left. Pass head (which now ends at prev). This builds the left subtree.
6. Recurse right. Pass slow.next. This builds the right subtree.

Complexity analysis

Time: O(n log n). At each level of recursion, you scan through all the nodes at that level to find middles. There are O(log n) levels (the tree is balanced), and each level processes a total of O(n) nodes across all sublists. That gives O(n log n) total.

Space: O(log n). The recursion depth is O(log n) because the list is halved at each step. No extra data structures are used beyond the call stack and the output tree.

The array approach trades space for speed. Converting the list to an array lets you index the middle in O(1), bringing time down to O(n). But the linked list approach is what interviewers are testing: can you work with the list directly?

Edge cases

• Empty list (head is null). Return null immediately. The base case handles this.
• Single node. Return a TreeNode with that value. It is both the root and a leaf.
• Two nodes. The slow/fast scan stops with slow at the second node. The first node becomes the left child. There is no right child. The tree is still balanced (heights differ by 1).

The building blocks

This problem is built from two core building blocks:

Slow/fast pointer for finding the middle. Two pointers moving at different speeds through a linked list. When the fast pointer reaches the end, the slow pointer is at the midpoint. This is the same technique used in Linked List Cycle (LeetCode 141), Reorder List (LeetCode 143), and Palindrome Linked List (LeetCode 234). The twist here is that you also need a prev pointer to cut the list in half.

Recursive tree construction from sorted data. The pattern of picking the middle element as root and recursing on each half is identical to Convert Sorted Array to BST (LeetCode 108). The only difference is how you access the middle: array indexing vs. slow/fast traversal. Once you recognize this pattern, any sorted-data-to-BST problem follows the same shape.

These two building blocks combine cleanly. The slow/fast scan gives you the split point. The recursive construction gives you the tree. Neither piece is complicated on its own, but combining them smoothly under pressure is what makes this a medium-level problem.

From understanding to recall

You understand the algorithm now. The slow/fast pointer finds the middle, you cut the list, you recurse. But understanding and being able to reproduce it from scratch are different things.

The details that trip people up: initializing prev to null, remembering to cut with prev.next = None, handling the single-node base case before starting the scan, and passing slow.next (not slow) for the right subtree. These are the kind of small mistakes that cost you time in an interview.

The fix is repetition with spacing. Type the solution from memory, check it, and come back in a few days. After three or four reps, the pointer manipulation becomes automatic.

Related posts

• Convert Sorted Array to BST - The array version of this problem, where you can index into the middle directly
• Linked List Cycle - The classic slow/fast pointer problem that introduces Floyd's tortoise and hare technique