Convert Sorted List to BST — In-Order O(n) Build

Problem 247 · Convert Sorted List to BST (O(n) In-Order)

Difficulty: Hard · Pattern: In-Order Construction

Build BST in O(n) by simulating in-order traversal and consuming list nodes as we go (instead of O(n log n) find-middle approach).

Intuition

Count n → recurse like binary search on indices → at leaf, consume the current list node.

Solutions

# Python
def sortedListToBST(head):
    n = 0; cur = head
    while cur: n += 1; cur = cur.next

    self_node = [head]  # use list to allow mutation in closure

    def build(lo, hi):
        if lo > hi: return None
        mid = (lo + hi) // 2
        left = build(lo, mid - 1)
        root = TreeNode(self_node[0].val)
        self_node[0] = self_node[0].next
        root.left = left
        root.right = build(mid + 1, hi)
        return root

    return build(0, n - 1)

// Java
ListNode cur;
public TreeNode sortedListToBST(ListNode head) {
    cur = head; int n = 0;
    while (head != null) { n++; head = head.next; }
    return build(0, n-1);
}
TreeNode build(int lo, int hi) {
    if (lo > hi) return null;
    int mid = (lo + hi) / 2;
    TreeNode left = build(lo, mid-1);
    TreeNode root = new TreeNode(cur.val);
    cur = cur.next;
    root.left = left;
    root.right = build(mid+1, hi);
    return root;
}

Complexity

Time: O(n)
Space: O(log n) recursive stack