Convert Sorted List to Binary Search Tree

Intuition

Unlike an array, a linked list gives no O(1) access to the middle, so repeatedly scanning for a midpoint would be wasteful. The trick is to notice that an inorder traversal of the target BST visits values in exactly the same order as the sorted list. So we first count the length to learn the shape of a balanced tree, then perform a simulated inorder build: recurse into the left half first, then consume the current list node as the subtree root, then recurse into the right half. A single moving pointer advances through the list in lockstep with the inorder visits, so every list node is used once and in order. This turns an otherwise O(n log n) approach into a clean linear-time construction.

Algorithm walkthrough

1. 1Walk the list once to compute its length n; this defines the index range [0, n - 1].
2. 2Keep a moving pointer current, initialised to head, that always points at the next value to place.
3. 3Define build(left, right); if left > right, return null for an empty range.
4. 4Recurse into the left half [left, mid - 1] first so earlier list values are consumed before the root.
5. 5Create the current node from current.val, advance current to its next, then recurse into the right half [mid + 1, right].
6. 6Return the node; build(0, n - 1) yields the balanced BST root.

Implementation

class Solution:
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        size = 0
        node = head
        while node:
            size += 1
            node = node.next

        self.current = head

        def build(left: int, right: int) -> Optional[TreeNode]:
            if left > right:
                return None
            mid = left + (right - left) // 2
            left_child = build(left, mid - 1)
            root = TreeNode(self.current.val)
            root.left = left_child
            self.current = self.current.next
            root.right = build(mid + 1, right)
            return root

        return build(0, size - 1)