Convert Sorted List to Binary Search Tree
Problem
head of a singly linked list sorted in ascending order.
Build a height-balanced binary search tree (every node's subtrees differ in height by at
most 1) that contains exactly these values and return its root. Any valid balanced BST is accepted.[-10,-3,0,5,9]Output[0,-3,9,-10,null,5][]Output[]0 ≤ n ≤ 2·104 · -105 ≤ Node.val ≤ 105 · list is sorted ascending
Try it yourself
class Solution {
public TreeNode sortedListToBST(ListNode head) {
}
}
Instinct If the answer for n items can be built from the same problem on halves (or smaller pieces) plus a cheap combine step - split, recurse, merge.
Memory hack Split it, trust it, stitch it - nail the base case, take the leap of faith on smaller calls, then glue their answers together.
Open the Recursion & Divide and Conquer guide →Approaches
Brute ForceFind Middle with Slow/Fast Each Call
O(n log n)Space O(log n)Treat [head, tail) as the current sub-list. Slow/fast pointers find its
middle, which becomes the root; recurse on [head, mid) and
[mid.next, tail). Each recursion level walks O(n) nodes in total, and there
are O(log n) levels.
public TreeNode sortedListToBST(ListNode head) { return build(head, null); } private TreeNode build(ListNode head, ListNode tail) { if (head == tail) return null; ListNode slow = head, fast = head; while (fast != tail && fast.next != tail) { slow = slow.next; fast = fast.next.next; } TreeNode root = new TreeNode(slow.val); root.left = build(head, slow); root.right = build(slow.next, tail); return root; }
No extra memory besides the recursion, but re-scans the list on every level.
BetterCopy to Array, then Binary Split
O(n)Space O(n)Linked lists lack random access, so copy the values into an array first. Then the
middle of any range is O(1): mid = (l + r) / 2 becomes the root and the two
sides become subtrees (the classic “sorted array to BST”).
public TreeNode sortedListToBST(ListNode head) { List<Integer> vals = new ArrayList<>(); for (ListNode p = head; p != null; p = p.next) vals.add(p.val); return build(vals, 0, vals.size() - 1); } private TreeNode build(List<Integer> vals, int l, int r) { if (l > r) return null; int mid = (l + r) >>> 1; TreeNode root = new TreeNode(vals.get(mid)); root.left = build(vals, l, mid - 1); root.right = build(vals, mid + 1, r); return root; }
Linear time, but trades it for an O(n) copy of the list.
OptimalInorder Simulation (Consume the List)
O(n)Space O(log n)Count the nodes, then build over index range [l, r] in inorder:
first the whole left subtree (which consumes exactly mid - l nodes), then
the root from the current list node, advance it, then the right subtree. The list
pointer is always at the right value — no searching at all.
private ListNode cur; public TreeNode sortedListToBST(ListNode head) { int n = 0; for (ListNode p = head; p != null; p = p.next) n++; cur = head; return build(0, n - 1); } private TreeNode build(int l, int r) { if (l > r) return null; int mid = (l + r) >>> 1; TreeNode left = build(l, mid - 1); // consumes the left half TreeNode root = new TreeNode(cur.val); cur = cur.next; root.left = left; root.right = build(mid + 1, r); return root; }
Linear time and only the O(log n) recursion stack — best of both.
cur pointer, so the tree is built bottom-up, left to right.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Find Middle with Slow/Fast Each Call | O(n log n) | O(log n) |
| Better | Copy to Array, then Binary Split | O(n) | O(n) |
| Optimal | Inorder Simulation (Consume the List) | O(n) | O(log n) |
- Slow/fast loop that ignores
tail— the middle is found in the wrong range. - Inorder version: creating the root before building the left subtree takes the wrong value.
- Not cutting/limiting the range — infinite recursion on a 1-node sub-list.
- Start from “sorted array to BST” (LC 108) and ask what changes without random access.
- Explain why the slow/fast version is O(n log n): O(n) scanning per level, log n levels.
- Present the inorder trick as the follow-up that removes both the scan and the array.