Convert Sorted List to BST
Turn a sorted linked list into a height-balanced BST.
- The number of nodes in head is in the range [0, 2 * 10⁴].
- -10⁵ <= Node.val <= 10⁵
Intuition
To convert sorted list to bst and keep the result height-balanced, the root must be the middle element — that is what splits the remaining values evenly between the two subtrees, and doing it at every level is what keeps the height at O(log n). The obvious implementation finds the middle with a slow-and-fast pointer walk, builds a node, then recurses on each half. It is correct, but each level re-walks the list to find its middles, giving O(n log n). The faster approach comes from noticing which order the values are needed in. An inorder traversal of the finished BST visits nodes in ascending order — which is precisely the order the sorted list already holds. So rather than seeking positions in the list, build the tree in inorder and consume the list left to right as you go. That means the recursion works on sizes, not values: - Build the left subtree first, then take the next list node as the root, then build the right subtree. When the left subtree is finished, the list pointer is sitting exactly on the value that belongs at this root. Take it, advance once, and continue. Each node is consumed exactly once, so the whole build is O(n) with a single forward pass over the list — no repeated searching, and no need to know a value before its node is created.
To convert sorted linked list to bst, build the tree in inorder while walking the list forward. Since inorder traversal of a BST visits values in sorted order — exactly the list's order — the node is created at the moment between the two recursive calls, and the list pointer advances once per node.
Approach
Before reading on: price up what the direct approach costs here, then ask what each node needs from its children before it can answer. Aim for O(n) time and O(log n) space.
Count the list length first
One pass gives n. The recursion then works purely with position counts, never needing to look ahead in the list — which is what removes the repeated middle-finding walks.
Recurse on sizes, not on values
Define build(left, right) over positions. Compute the midpoint, build the left subtree from left..mid-1, then create the current node, then build the right from mid+1..right. The node is created between the two recursive calls, not before them.
Consume the list in inorder
When the left subtree finishes, the shared list pointer is on exactly the value this node needs. Take it, advance the pointer once, and continue. This ordering is the crux — taking the value before recursing left assigns every node the wrong key.
Stop on an empty range
When left exceeds right there are no positions to fill, so return null without consuming a list node. This terminates every branch and handles the empty list without a special case.
Balance comes free from the midpoint
Splitting the size range in half at each level means the two subtrees differ in size by at most one, so the height is ⌈log n⌉. Balance is guaranteed by construction rather than checked afterwards.
Cost compared with the naive version
Each list node is visited exactly once, giving O(n) time against O(n log n) for repeatedly finding middles. Space is O(log n) for the recursion stack on the balanced tree being built.
Solution & live demo
Common pitfalls
Finding the middle node for every subtree
slow, fast = head, head # find middle, recurse on both halves
left = build(l, mid - 1) node = TreeNode(self.cur.val) self.cur = self.cur.next
Repeated middle-finding costs O(n log n) because each level rescans. Building in inorder touches each node once — O(n) — since the list order already is the inorder sequence.
Creating the node before recursing left
node = TreeNode(self.cur.val) self.cur = self.cur.next node.left = build(l, mid - 1)
left = build(l, mid - 1) node = TreeNode(self.cur.val)
That consumes the list in preorder, so the smallest values land at internal nodes rather than the left spine and the result isn't a BST. The node must be taken at the inorder moment — after the left subtree is complete.
Converting to an array first
vals = [] while head: vals.append(head.val); head = head.next
n, cur = 0, head while cur: n += 1; cur = cur.next
Works, but allocates O(n) extra space when only the count is needed. The list itself is consumed in order by the inorder build, so the values never need copying.
Edge cases
n=0 → None.
Either middle works; mid = (l+r)//2 picks consistently.