Convert Sorted List to BST — O(n) In-Order Construction Explained

Problem Statement#

LeetCode 109 — Convert Sorted List to Binary Search Tree (O(n) In-Order) Difficulty: Hard | Pattern: In-Order BST Construction

Given the head of a singly linked list where elements are sorted in ascending order, convert it to a height-balanced BST. This version focuses on the optimal O(n) approach using in-order construction, improving on the O(n log n) fast/slow midpoint approach covered in the previous post.

Constraints:

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

Example:

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

Why This Problem Matters#

The O(n) in-order construction of a BST from a sorted linked list is a technique that showcases advanced recursion thinking. While the O(n log n) approach (finding the midpoint at each level) is immediately intuitive, the O(n) approach requires a deeper insight: simulate the in-order traversal of the BST and consume list nodes in sequence.

This technique is asked at Amazon, Google, and Microsoft in senior-level interviews as a follow-up to "can you do better than O(n log n)?" Most candidates know the midpoint approach. Fewer know the in-order simulation. Being able to explain and implement the O(n) approach signals strong algorithmic depth.

The insight transfers to other problems: whenever you need to build a data structure from a sorted input, consider whether you can simulate the traversal of that data structure and consume the sorted input in the natural traversal order, rather than repeatedly dividing and finding midpoints.

This approach also appears in the construction of Cartesian trees, B-trees, and segment trees from sorted arrays.

The Core Insight#

Key observation: When you perform an in-order traversal of a BST (left -> root -> right), the nodes are visited in sorted order. If you build the BST by simulating this in-order traversal and consuming the sorted linked list nodes sequentially, each node is processed exactly once — giving O(n) time.

The algorithm:

1. Count the total number of nodes n.
2. Recursively build the BST for the index range [lo, hi] (indices into the sorted sequence).
3. For any range [lo, hi], the root is at the mid index (lo + hi) // 2.
4. Build the left subtree first (in-order: left before root).
5. Consume the current list node as the root (the list pointer advances automatically).
6. Build the right subtree.

Because we always build left before root, and the list is sorted in ascending order, we consume list nodes in exactly the right order — the smallest values go to the leftmost nodes, which corresponds to in-order traversal.

Visual Dry Run#

Input: [-10, -3, 0, 5, 9] (n=5)

Recursion tree (index ranges):

build(0, 4):
  mid = 2
  LEFT: build(0, 1)   -> consume -10 and -3
    mid = 0
    LEFT: build(0, -1) -> null (base case)
    ROOT: consume -10  -> TreeNode(-10)
    RIGHT: build(1, 1)
      mid = 1
      LEFT: build(1, 0) -> null
      ROOT: consume -3  -> TreeNode(-3)
      RIGHT: build(2, 1) -> null
  ROOT: consume 0    -> TreeNode(0)
  RIGHT: build(3, 4)   -> consume 5 and 9
    mid = 3
    LEFT: build(3, 2) -> null
    ROOT: consume 5   -> TreeNode(5)
    RIGHT: build(4, 4)
      mid = 4
      LEFT: build(4, 3) -> null
      ROOT: consume 9   -> TreeNode(9)
      RIGHT: build(5, 4) -> null

List consumption order: -10, -3, 0, 5, 9 (exactly in-order!)

Result:

      0
     / \
   -3   9
   /   /
 -10  5

Solution (Optimal — O(n) In-Order)#

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]:
    # Count total nodes
    n = 0
    curr = head
    while curr:
        n += 1
        curr = curr.next
 
    # Use a mutable reference to advance through the list
    # (Python needs a container since integers are immutable in closures)
    self_curr = [head]
 
    def build(lo: int, hi: int) -> Optional[TreeNode]:
        if lo > hi:
            return None
 
        mid = (lo + hi) // 2
 
        # Build LEFT subtree first (in-order: consume smaller values first)
        left = build(lo, mid - 1)
 
        # Consume current list node as root
        root = TreeNode(self_curr[0].val)
        self_curr[0] = self_curr[0].next  # advance list pointer
 
        # Build RIGHT subtree
        root.left = left
        root.right = build(mid + 1, hi)
 
        return root
 
    return build(0, n - 1)

function sortedListToBST(head) {
    // Count total nodes
    let n = 0;
    let curr = head;
    while (curr) { n++; curr = curr.next; }
 
    // Use an object to hold mutable curr reference
    const state = { curr: head };
 
    function build(lo, hi) {
        if (lo > hi) return null;
 
        const mid = Math.floor((lo + hi) / 2);
 
        // Build left subtree first (in-order)
        const left = build(lo, mid - 1);
 
        // Consume current node as root
        const root = { val: state.curr.val, left: null, right: null };
        state.curr = state.curr.next;
 
        // Build right subtree
        root.left = left;
        root.right = build(mid + 1, hi);
 
        return root;
    }
 
    return build(0, n - 1);
}

Complexity:

Comparison with O(n log n) approach:

Common Mistakes#

1. Building right before left: The in-order simulation requires building left before consuming the root and building right. Swapping the order produces incorrect node assignments.
2. Not using a mutable list pointer: In Python, integers are immutable in closures. Use a list [head] or class attribute to allow the inner function to advance the pointer.
3. Using range-based splitting instead of in-order: Candidates who understand the approach but implement it by finding the midpoint node at each step get O(n log n), not O(n). The in-order approach never finds the midpoint — it just knows the mid INDEX.
4. Off-by-one in the range: build(lo, mid - 1) for left and build(mid + 1, hi) for right. The mid index is the current root — it must not be included in either subtree's range.
5. Not counting nodes first: The in-order approach requires knowing n upfront to define the index ranges. Forgetting this step breaks the algorithm.

Interview Tips#

• Present this as an upgrade: "The O(n log n) approach finds the midpoint at each level using fast/slow pointers. I can improve to O(n) by simulating in-order traversal."
• Explain the key insight clearly: "An in-order traversal of the BST visits nodes in sorted order. So if I build the BST by simulating in-order traversal, I consume the sorted list exactly in sequence."
• Trace the consumption order: Walk through the recursion tree and show that nodes are consumed as -10, -3, 0, 5, 9 — exactly left-to-right order in the input list.
• Explain the mutable pointer trick: "I need a mutable reference to the list head so the inner function can advance it. In Python, I use a list wrapper."
• Contrast with midpoint approach: "The midpoint approach finds the mid node by traversal — O(n) work per level. The in-order approach does O(1) work per node — just consume and build."

Follow-up Questions#

1. LeetCode 38 / 109 (midpoint approach): The O(n log n) version covered in the previous blog post. Know both.
2. LeetCode 108 — Convert Sorted Array to BST: The array version — O(n) time is easier since midpoint access is O(1).
3. Build a red-black tree or AVL tree from sorted input: Same in-order simulation principle, but with additional balancing rotations.
4. What if the list had duplicates? You would need to decide the BST invariant (strict inequalities or allow duplicates) and adjust accordingly.
5. Reconstruct a BST from its in-order traversal: This problem in reverse — given in-order values, build any valid BST (not necessarily balanced).

Key Takeaways#

• In-order traversal of a BST produces sorted output. Reversing this: building the BST by simulating in-order traversal and consuming sorted input in sequence gives O(n) time.
• Count n first to define index ranges [lo, hi]. The root of each subproblem is at the midpoint index — but you never access it directly; you consume the next list node.
• Always build the left subtree before consuming the root — this ensures the list pointer is at the correct node when you create the root.
• Use a mutable reference (list wrapper in Python, object in JavaScript) to allow the list pointer to advance across recursive calls.
• Time is O(n) — each node is consumed exactly once. Space is O(log n) for the recursion stack.
• This technique generalizes to any scenario where you build a balanced tree from a sorted sequence and want to consume each element exactly once.