Free lesson · DSA Mastery - Interview Prep, End to End

Convert Sorted List to Binary Search Tree

Medium10 min readdsadivide-and-conquer

Convert Sorted List to Binary Search Tree

Convert Sorted List to Binary Search Tree applies divide and conquer to tree construction: turn a sorted linked list into a height-balanced binary search tree. The divide step picks the middle element as the root, so the elements before it become a balanced left subtree and those after become a balanced right subtree. Here the split point - the midpoint - defines the tree's shape, and balance falls out of the divide strategy itself: always rooting at the middle guarantees the two sides differ in size by at most one at every level. We present three approaches: the simple "convert to array first" version, the slow/fast-pointer version that works on the list directly, and the elegant inorder-simulation version that builds the tree in a single O(n) pass.

The insight: a sorted sequence becomes a balanced BST when you repeatedly choose the middle as the root. The middle splits the sequence into two halves of nearly equal size, and applying the same rule recursively to each half keeps every subtree balanced - the BST ordering is automatic because the input is already sorted.

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 binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Example 1:

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

Explanation: 0 is chosen as the root (middle element); [-10,-3] forms the left subtree,
[5,9] forms the right subtree.

Example 2:

Input:  head = []
Output: []

Constraints:

• The number of nodes in head is in the range [0, 2 * 10^4].
• -10^5 <= Node.val <= 10^5

Approaches Overview

Copying to an array makes midpoint access O(1) and gives clean O(n). The slow/fast approach avoids the array but re-walks to find each midpoint, costing O(n log n). The inorder simulation builds the tree left-to-right in sync with one list traversal - O(n) time and no array.

Approach 1: Copy to Array, Then Build

The Idea

Walk the list once into an array (random access). Then recursively build: the middle index is the root, the left half builds the left subtree, the right half builds the right subtree. Midpoint access is O(1), so the build is O(n) overall.

Logic Flowchart

graph TD
    A["copy list values into array a[]"] --> B["build(lo, hi)"]
    B --> C{"lo > hi?"}
    C -->|Yes| D["return null"]
    C -->|No| E["mid = (lo+hi)/2; root = a[mid]"]
    E --> F["root.left = build(lo, mid-1)"]
    F --> G["root.right = build(mid+1, hi)"]
    G --> H["return root"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style D fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style G fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style H fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the array approach. We copy the list into an array for random access, then recursively make the middle element the root and build the left and right subtrees from the two halves.

Code

public static TreeNode sortedListToBSTArray(ListNode head) {
    List<Integer> vals = new ArrayList<>();
    for (ListNode c = head; c != null; c = c.next) vals.add(c.val);
    return build(vals, 0, vals.size() - 1);
}

private static TreeNode build(List<Integer> a, int lo, int hi) {
    if (lo > hi) return null;                    // empty range
    int mid = lo + (hi - lo) / 2;
    TreeNode root = new TreeNode(a.get(mid));    // middle is the root
    root.left  = build(a, lo, mid - 1);          // left half -> left subtree
    root.right = build(a, mid + 1, hi);          // right half -> right subtree
    return root;
}

// TreeNode: int val; TreeNode left, right;
// Usage: sortedListToBSTArray([-10,-3,0,5,9]) -> balanced BST rooted at 0

This Java code copies the list into an array, then recursively builds a balanced tree by taking the middle element as the root and constructing the left and right subtrees from the surrounding halves.

Complexity

Time: O(n) - one copy pass plus O(1) midpoint per node. Space: O(n) for the array plus O(log n) recursion.

Approach 2: Slow/Fast Pointer to Find Middle

The Idea

Avoid the array by finding the middle of the (sub)list with slow/fast pointers each time: slow advances one step, fast two, so slow lands on the middle. That node becomes the root; recurse on the list before it and the list after it. Finding the middle is O(k) for a length-k sublist, and there are log n levels of O(n) total work → O(n log n).

Logic Flowchart

graph TD
    A["build(head, tail)"] --> B{"head == tail?"}
    B -->|Yes| C["return null (empty range)"]
    B -->|No| D["slow/fast from head to find mid"]
    D --> E["root = new TreeNode(mid.val)"]
    E --> F["root.left = build(head, mid)"]
    F --> G["root.right = build(mid.next, tail)"]
    G --> H["return root"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style G fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style H fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the slow-fast approach. For each sublist, slow and fast pointers locate the middle node, which becomes the root; the sublists before and after it build the left and right subtrees.

Code

public static TreeNode sortedListToBST(ListNode head) {
    return build(head, null);
}

// build a BST from the half-open list range [head, tail)
private static TreeNode build(ListNode head, ListNode tail) {
    if (head == tail) return null;               // empty range
    ListNode slow = head, fast = head;
    while (fast != tail && fast.next != tail) {  // find middle of [head, tail)
        slow = slow.next;
        fast = fast.next.next;
    }
    TreeNode root = new TreeNode(slow.val);      // middle node is the root
    root.left  = build(head, slow);              // nodes before middle
    root.right = build(slow.next, tail);         // nodes after middle
    return root;
}

This Java code finds the middle of each half-open list range with slow and fast pointers, makes it the root, and recursively builds the left subtree from the nodes before it and the right subtree from the nodes after it.

Complexity

Time: O(n log n) - finding each midpoint re-walks the sublist. Space: O(log n) recursion stack.

Approach 3: Inorder Simulation (Build in One Pass) - Optimal

The Idea

The clever observation: an inorder traversal of a BST visits nodes in sorted order - exactly the order of the list. So build the tree in the same order you consume the list. First count n. Then recursively build by index range [lo, hi]: build the left subtree first (consuming the smaller values), then take the current list node as the root and advance the list pointer, then build the right subtree. Because construction follows inorder, each list node is consumed exactly once, in order - O(n) with no array and no repeated midpoint scans.

Logic Flowchart

graph TD
    A["count n; cur = head"] --> B["build(lo, hi)"]
    B --> C{"lo > hi?"}
    C -->|Yes| D["return null"]
    C -->|No| E["mid = (lo+hi)/2"]
    E --> F["left = build(lo, mid-1)  (consume smaller values first)"]
    F --> G["root = new TreeNode(cur.val); cur = cur.next"]
    G --> H["root.left = left; root.right = build(mid+1, hi)"]
    H --> I["return root"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style D fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style G fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style H fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style I fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the inorder simulation. We build the left subtree first, then consume the current list node as the root and advance the pointer, then build the right subtree. Because construction follows inorder, list nodes are consumed in sorted order in a single pass.

Code

public class ListToBST {
    private ListNode cur;

    public TreeNode sortedListToBST(ListNode head) {
        int n = 0;
        for (ListNode c = head; c != null; c = c.next) n++;
        cur = head;
        return build(0, n - 1);
    }

    private TreeNode build(int lo, int hi) {
        if (lo > hi) return null;
        int mid = lo + (hi - lo) / 2;
        TreeNode left = build(lo, mid - 1);      // build left subtree first (inorder)
        TreeNode root = new TreeNode(cur.val);   // current node is this root
        cur = cur.next;                          // advance list in sorted order
        root.left = left;
        root.right = build(mid + 1, hi);         // then build right subtree
        return root;
    }
}

// Usage:
// new ListToBST().sortedListToBST([-10,-3,0,5,9]) -> balanced BST

This Java code counts the list length, then builds the tree by index range. It constructs the left subtree first, takes the current list node as the root and advances the pointer, then builds the right subtree, so the list is consumed in sorted order in one pass.

Step-by-Step Walkthrough

A frame-by-frame trace on head = [-10,-3,0,5,9] (n=5, indices 0–4):

graph LR
    F0["build(0,4) mid2: build left(0,1) first"]
    F1["left(0,1) mid0: left(0,-1)=null; root=cur(-10) adv; right(1,1)"]
    F2["right(1,1) mid1: root=cur(-3) adv → so left subtree root -10 with right child -3"]
    F3["back: root=cur(0) adv (the middle value); right(3,4): root 5, right child 9"]
    F4["balanced BST rooted at 0"]
    F0 --> F1 --> F2 --> F3 --> F4

    style F0 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F1 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F2 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F4 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough builds a balanced tree from minus ten, minus three, zero, five, nine. Construction follows inorder: the left subtree consumes minus ten and minus three, then zero becomes the root, then the right subtree consumes five and nine, all in a single sorted pass through the list.

Result: a height-balanced BST rooted at 0.

Complexity

Time: O(n) - one count pass plus one construction pass. Space: O(log n) recursion stack (balanced tree depth).

Complexity Comparison

All three pick the middle as the root, so all produce a height-balanced BST. The array version is the easiest; the inorder simulation is the most elegant - it recognizes that BST construction can follow the list's natural order, achieving O(n) without an array. The slow/fast version is a nice "work on the list directly" middle ground.

Variations & Follow-ups

Why does choosing the middle as the root guarantee balance?

The middle splits a size-k range into halves of size ⌊(k-1)/2⌋ and ⌈(k-1)/2⌉, which differ by at most one. Applying this recursively, every node's two subtrees differ in size by at most one, and the height is O(log n). Picking any other element as root could make one side much larger, breaking the height-balance guarantee.

Why is the inorder simulation O(n) when the slow/fast version is O(n log n)?

The slow/fast version re-walks each sublist to find its midpoint, repeating work across the log n levels → O(n log n). The inorder simulation never searches for a midpoint: it walks the list exactly once, consuming each node as the recursion reaches its inorder position. No repeated traversal means linear time.

How does the inorder trick work conceptually?

A BST's inorder traversal yields sorted values, and the list is already sorted - so the order in which nodes should be assigned values is exactly the list order. By building the left subtree before reading the current node and the right subtree after, the recursion visits "slots" in inorder, letting you fill them straight from the list pointer.

If the input were a sorted array instead of a list, which approach is best?

The array gives O(1) midpoint access, so the direct "middle as root" recursion (Approach 1 without the copy step) is already O(n) and simplest - that's the classic "Convert Sorted Array to BST" problem. The list version is harder precisely because a list has no random access, which is what motivates the slow/fast and inorder techniques.

What about edge cases?

• Empty list (Example 2): Returns null.
• Single node: Becomes a single-node tree (it's the middle).
• Two nodes: One becomes the root, the other a child - still height-balanced (heights differ by one).
• Even length: lo + (hi-lo)/2 picks the lower-middle; any consistent choice yields a valid balanced tree.

Common Interview Pitfalls

• Re-finding the middle by re-walking (then claiming O(n)). That's O(n log n); only the array or inorder approach is truly linear.
• Off-by-one in the list range. Using a half-open [head, tail) range avoids confusion about which node is excluded.
• Forgetting to advance the list pointer in the inorder version. The cur = cur.next after reading the root is essential.
• Producing a valid BST but not balanced. You must root at the middle; rooting at the head builds a degenerate (linked-list-shaped) tree.

Why This Topic Matters

Convert Sorted List to BST shows divide and conquer where the split point defines the output structure - choosing the middle as the root is what makes the tree balanced. It also showcases a beautiful combine optimization (the inorder simulation) that turns O(n log n) into O(n) by aligning construction order with the data's natural order. Both ideas - split to shape the result, and align traversal order with construction - recur throughout tree algorithms.

The next topic, Construct Quad Tree, takes divide and conquer into two dimensions with a four-way split: represent a grid as a quad tree by recursively dividing it into four quadrants. If a region is uniform (all 0s or all 1s) it becomes a leaf; otherwise it becomes an internal node with four children, one per quadrant, each built recursively. The combine step even merges four uniform leaves of the same value back into a single leaf - a divide-and-conquer with a four-way branch and a merging combine.

Back to DSA Mastery - Interview Prep, End to End