LeetCode #109 Medium

Convert Sorted List to BST

Turn a sorted linked list into a height-balanced BST.

bstlinked-listdivide-and-conquer

02

Intuition

Balance demands the middle element as root. Finding the middle of a list repeatedly costs O(n log n) — instead, build inorder: recurse on sizes, consume list nodes left-to-right exactly when the inorder traversal would visit them. The list pointer advances once per node, total O(n).

How to spot this pattern

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.

03

Approach

1

Sizes first

Count the list length n. build(l, r) constructs the subtree covering positions l..r without knowing values in advance.

2

Inorder consumption

Build the left subtree, THEN take the current list node as root (advance the pointer), then build the right — values arrive in exactly the right order.

3

Balanced by construction

Midpoint split of sizes guarantees height ⌈log n⌉.

04

Solution & live demo

▶1class Solution:
▶2    def sortedListToBST(self, head):
▶3        n, cur = 0, head
▶4        while cur: n += 1; cur = cur.next
▶5        self.cur = head
▶6        def build(l, r):
▶7            if l > r: return None
▶8            mid = (l + r) // 2
▶9            left = build(l, mid - 1)
▶10            node = TreeNode(self.cur.val)   # inorder moment
▶11            self.cur = self.cur.next
▶12            node.left = left
▶13            node.right = build(mid + 1, r)
▶14            return node
▶15        return build(0, n - 1)

05

Common pitfalls

Finding the middle node for every subtree

✗ Wrong

slow, fast = head, head
# find middle, recurse on both halves

✓ Right

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

✗ Wrong

node = TreeNode(self.cur.val)
self.cur = self.cur.next
node.left = build(l, mid - 1)

✓ Right

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

✗ Wrong

vals = []
while head: vals.append(head.val); head = head.next

✓ Right

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.

06

Edge cases

Empty list

n=0 → None.

Even length

Either middle works; mid = (l+r)//2 picks consistently.

07

Complexity

Time

O(n)

Space

O(log n)

List consumed strictly in order.