Sorted List to Balanced BST

Interview Problem Interview Medium Binary Search Tree Linked List Divide and Conquer

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.sortedListToBST(head). Convert the ascending linked list to a height-balanced BST. Use the lower midpoint of each value interval for deterministic Judge output.

Starter code

class Solution:
    def sortedListToBST(self, head):
        pass

Test cases

five-values

{
  "args": [
    {
      "$type": "linked-list",
      "values": [
        -10,
        -3,
        0,
        5,
        9
      ]
    }
  ]
}

Expected: {"$type":"binary-tree","values":[0,-10,5,null,-3,null,9]}

Wizard outline

Step 1: Initialize Solution.sortedListToBST
Replace the empty starter with the first real state owned by Solution.sortedListToBST. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Assemble the primary transition
Extend the initialized state with the next contiguous part of the popular solution. The transition explains how one input element or operation changes the state; boundaries are easier to reason about after this invariant is visible.
Step 3: Pass the One Value case
Complete the readable core algorithm for one representative Interview case. Copy sorted values once and recursively choose interval midpoints as balanced roots.
Step 4: Harden the Five Values boundary
Repair the reviewed boundary and pass the complete submission contract. In-order traversal visits the recursively built left interval, midpoint, then right interval, reproducing sorted values and the BST invariant. Midpoint splits differ by at most one, so every subtree is height-balanced.

Footguns and prerequisites

Use inclusive interval bounds consistently and stop when left exceeds right.
linked lists
trees and graphs

Reviewed references

LeetCode 109 — Convert Sorted List to Binary Search Tree

Practice prerequisites

Partition Traversal Ranges(opens in a new tab)
Partition Traversal Ranges isolates each frame describes matching node sets, and the inorder root offset determines the exact left-subtree size in preorder. That focused state discipline is required when implementing sorted list to bst as a complete Interview Problem.
Trace Fast and Slow Pointers(opens in a new tab)
Trace Fast and Slow Pointers isolates after each loop, slow has advanced one link for every two links attempted by fast. That focused state discipline is required when implementing sorted list to bst as a complete Interview Problem.

Recommended approach and implementation

Copy list values into an array, then recursively build each inclusive interval from its lower midpoint.

Why it works: In-order traversal visits the recursively built left interval, midpoint, then right interval, reproducing sorted values and the BST invariant. Midpoint splits differ by at most one, so every subtree is height-balanced.

class Solution:
    def sortedListToBST(self, head):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        values = []
        while head:
            values.append(head.val)
            head = head.next
        def build(left, right):
            if left > right: return None
            middle = (left + right) // 2
            node = TreeNode(values[middle])
            node.left = build(left, middle - 1)
            node.right = build(middle + 1, right)
            return node
        return build(0, len(values) - 1)