DSA problem
Convert Sorted List to Binary Search Tree
Given the head of a singly linked list whose elements are sorted in ascending order, convert it to a height-balanced binary search tree. A binary search tree is height-balanced when, for every node, the depths of its two subtrees differ by at most one.
The defining property of a balanced BST built from a sorted sequence is that the root must be (close to) the middle element. Everything to its left becomes the left subtree, everything to its right becomes the right subtree, and the same rule is applied recursively. This is the classic divide-and-conquer recipe: divide the sorted input at its midpoint, conquer each half recursively, and combine by attaching the two recursively built subtrees to the root.
The complication compared to the array version of this problem is random access: a linked list cannot jump to its midpoint in O(1). Two clean techniques handle that. The first finds the middle in each recursive call using the slow/fast two-pointer trick, severing the list before the middle and recursing on the prefix and suffix. This runs in O(n log n) time because each of the log n levels touches O(n) nodes via the slow/fast walk.
A faster O(n) approach precomputes the length, then performs an inorder simulation: it advances a shared list pointer left-to-right while the recursion descends through the implicit balanced tree of indices [0, n-1]. Each list node is visited exactly once, the implicit recursion still produces a tree of height ⌈log₂(n+1)⌉, and the structure is therefore optimal. We show the slow/fast variant as the canonical implementation because it directly mirrors the divide-and-conquer mental model — find the middle, build the tree around it.
Examples
head = [-10,-3,0,5,9][0,-3,9,-10,null,5]head = [][]head = [1,3][3,1]Constraints
- The number of nodes in head is in the range [0, 2 * 10^4].
- -10^5 <= Node.val <= 10^5
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.