Convert Sorted List to BST — Fast/Slow Pointer Recursion Explained

Problem Statement#

LeetCode 109 — Convert Sorted List to Binary Search Tree Difficulty: Medium | Pattern: Fast/Slow Pointer + Recursive Divide and Conquer

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.

Constraints:

• Number of nodes: 0 <= n <= 2 * 10^4
• -10^5 <= Node.val <= 10^5

Example 1:

Input:  head = [-10, -3, 0, 5, 9]
Output: [0, -3, 9, -10, null, 5]
(One valid height-balanced BST:)
      0
     / \
   -3   9
   /   /
 -10  5

Example 2:

Input:  head = []
Output: []

Why This Problem Matters#

This problem is a direct bridge between two foundational data structures: sorted linked lists and binary search trees. It appears frequently at Amazon, Google, and Microsoft in the context of database indexing interviews ("how would you build a balanced index from a sorted stream of keys?") and data serialization discussions.

The challenge is that unlike "Convert Sorted Array to BST" (LC 108), you cannot jump to the middle with O(1) random access. You must find the midpoint by traversal — and this must be done efficiently for each recursive subproblem.

There are two approaches with very different complexity profiles:

Approach 1 — Find middle with fast/slow (O(n log n)): For each subproblem, walk to the midpoint using fast/slow pointers. The middle element becomes the root, and the two halves become recursive subproblems. This is the most intuitive approach and is completely acceptable in an interview.

Approach 2 — In-order construction (O(n)): Count nodes first, then use index-based recursion that consumes list nodes in sorted order (in-order traversal). This achieves optimal O(n) time but is harder to explain. It is covered in the next blog post.

The Core Insight#

For a height-balanced BST, the root should be the median of the sorted sequence. The left half becomes the left subtree and the right half becomes the right subtree — recursively.

The fast/slow pointer technique finds the median of a linked list in one traversal. To disconnect the left half so it can be recursed on independently, you also need to track the predecessor of slow:

prev -> slow -> ... -> fast

Set prev.next = null to disconnect the left half. Then:

• Left subproblem: head to prev (now terminated at null)
• Root: slow.val
• Right subproblem: slow.next

The base cases are null input (return null) and a single node (return a leaf with that value).

Visual Dry Run#

Input: [-10, -3, 0, 5, 9]

Level 0 — full list:

• fast/slow: slow lands on 0 (midpoint), prev = -3
• Disconnect: -3.next = null
• Root = 0
• Left sublist: [-10, -3], Right sublist: [5, 9]

Level 1 — Left [-10, -3]:

• slow lands on -3, prev = -10
• Disconnect: -10.next = null
• Root = -3
• Left: [-10], Right: null (no nodes after -3 since -3.next was set to null)

Wait — after disconnecting the right subproblem needs slow.next before disconnection. Let me be precise:

• Before disconnect: -10 -> -3 -> null (left sublist)
• slow ends at -3, prev = -10
• Left of -3: [-10] (head to prev.next = null after disconnect — we set -10.next = null)
• Right of -3: slow.next = null
• BST: -3 with left -10, right null

Level 1 — Right [5, 9]:

• slow lands on 9, prev = 5
• Root = 9
• Left: [5], Right: null

Final BST:

      0
     / \
   -3   9
   /   /
 -10  5

Solution (Approach 1 — Fast/Slow, O(n log n))#

from typing import Optional
 
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
def sortedListToBST(head: Optional[ListNode]) -> Optional[TreeNode]:
    # Base cases
    if not head:
        return None
    if not head.next:
        return TreeNode(head.val)
 
    # Find the middle node and its predecessor
    prev = None
    slow = head
    fast = head
    while fast and fast.next:
        prev = slow
        slow = slow.next
        fast = fast.next.next
 
    # Disconnect the left half
    if prev:
        prev.next = None
 
    # slow is the root; head to prev is the left sublist; slow.next is the right
    root = TreeNode(slow.val)
    root.left = sortedListToBST(head if prev else None)
    root.right = sortedListToBST(slow.next)
    return root

function sortedListToBST(head) {
    if (!head) return null;
    if (!head.next) return { val: head.val, left: null, right: null };
 
    // Find midpoint and predecessor
    let prev = null;
    let slow = head;
    let fast = head;
 
    while (fast && fast.next) {
        prev = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
 
    // Disconnect left half
    if (prev) prev.next = null;
 
    const root = { val: slow.val, left: null, right: null };
    root.left = sortedListToBST(prev ? head : null);
    root.right = sortedListToBST(slow.next);
    return root;
}

Complexity:

Common Mistakes#

1. Not tracking prev: Without prev, you cannot disconnect the left half. You will get an infinite recursion as the left sublist still contains the middle node.
2. Passing head when prev is null: If prev is null, it means the slow pointer never moved (single-node case, already handled), or the entire list is the right sublist — pass null for the left recursive call.
3. Forgetting slow.next after disconnecting: Capture slow.next BEFORE disconnecting if needed, since prev.next = null only affects the left side but slow.next is unaffected.
4. Not handling the empty list: Return null when head is null — this is the base case for empty sublists in the recursion.
5. Creating an unbalanced BST: If you always use the first or last element as the root (rather than the middle), the BST height approaches n instead of log n.

Interview Tips#

• State the approach clearly: "I'll use fast/slow pointers to find the median at each level of recursion, creating a balanced BST by always making the median the root."
• Explain why median ensures balance: "The median splits the list into two equal halves, so the left and right subtrees always differ in size by at most 1 — this guarantees height balance."
• Note the time complexity: "Finding the midpoint is O(n) per level, and there are O(log n) levels, so total is O(n log n). The O(n) in-order approach is faster but harder to explain on the fly."
• Offer the O(n) upgrade: "If you want optimal time, I can count nodes first and use in-order construction that processes each node exactly once."
• Verify with the example: Walk through [-10, -3, 0, 5, 9] to show the tree construction is correct and balanced.

Follow-up Questions#

1. LeetCode 108 — Convert Sorted Array to BST: The array version — O(n) time since you have random access to the midpoint.
2. Can you convert to a BST in O(n) time without extra space? Yes — use in-order construction (see next blog post, LC 42).
3. What if the list is not sorted? You would need to sort it first (O(n log n)) then convert — or build a balanced BST with insertions.
4. How do you verify the result is height-balanced? Write a helper that returns the height of a tree and checks that left and right heights differ by at most 1 at every node.
5. What if you wanted a maximum-branching BST instead of balanced? Always use the last element as root — you get a right-skewed tree (linked list).

Key Takeaways#

• The median of the sorted list is always the BST root — this ensures height balance by splitting into equal halves.
• Fast/slow pointers find the median in one traversal. Track the predecessor (prev) to disconnect the left half.
• Disconnect prev.next = null before recursing so the left sublist is terminated properly.
• Time is O(n log n) with this approach: O(n) to find the median at each of O(log n) recursion levels.
• The O(n) in-order construction approach (next blog post) counts nodes first and processes the list in one sequential pass — better time but harder to explain.
• This problem bridges two critical data structures — sorted linked lists and BSTs — and appears in database indexing and tree-building interview discussions.