LeetCode 109: Convert Sorted List to Binary Search Tree

Problem Restatement

We are given the head of a singly linked list whose values are sorted in ascending order.

We need to convert this sorted linked list into a height-balanced binary search tree.

The official problem defines a height-balanced binary tree as a binary tree where the depth difference between the two subtrees of every node never exceeds 1. (leetcode.com)

The resulting tree must satisfy the BST property:

left subtree values  < root value
right subtree values > root value

Input and Output

Item	Meaning
Input	`head`, the head of a sorted singly linked list
Output	The root of a height-balanced BST
List order	Ascending
Important condition	The resulting BST must be balanced
Linked list property	Sequential access only

LeetCode gives these classes:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

The function shape is:

class Solution:
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        ...

Examples

Consider the linked list:

-10 -> -3 -> 0 -> 5 -> 9

The middle value is:

This is a good root because it splits the values into two nearly equal halves.

Left half:

-10 -> -3

Right half:

5 -> 9

One valid BST is:

Another valid balanced BST is also acceptable.

For:

1 -> 3

One valid answer is:

    3
   /
  1

Another valid answer is:

    1
     \
      3

Both are balanced BSTs.

First Thought: Use the Middle Node as the Root

For a sorted array, we can directly access the middle index.

But a linked list does not support indexing.

So we need another way to find the middle value efficiently.

The standard method uses two pointers:

slow pointer
fast pointer

The slow pointer moves one step at a time.

The fast pointer moves two steps at a time.

When the fast pointer reaches the end, the slow pointer is at the middle node.

That middle node becomes the BST root.

Key Insight

The middle node naturally divides the linked list into:

left half
middle node
right half

Because the list is sorted:

left values  < middle value
right values > middle value

So the BST property automatically holds.

Then we recursively build:

left subtree  from left half
right subtree from right half

To isolate the left half, we disconnect the list before the middle node.

Algorithm

Define a recursive function:

build(head)

For each call:

If head is None, return None.
If the list contains only one node, return a leaf node.
Use slow and fast pointers to find the middle node.
Disconnect the left half from the middle node.
Create a tree node using the middle value.
Recursively build the left subtree from the left half.
Recursively build the right subtree from the nodes after the middle.
Return the root node.

The middle node is found using:

slow = head
fast = head

Then:

slow moves by 1
fast moves by 2

When the loop finishes, slow points to the middle node.

Correctness

The algorithm always chooses the middle node of the current linked list as the subtree root.

Since the linked list is sorted, every value before the middle node is smaller, and every value after the middle node is larger. Therefore, the BST property holds at the current root.

The algorithm disconnects the left half and recursively builds the left and right subtrees from the two remaining sublists. The same reasoning applies recursively to every subtree.

Because the middle node splits the list into two nearly equal halves, the sizes of the left and right subtrees differ by at most one node at each step. Therefore, the resulting tree is height-balanced.

When the list becomes empty, the algorithm returns None, correctly representing a missing child. When the list contains one node, the algorithm returns a leaf node.

Thus, the final tree is both a valid binary search tree and height-balanced.

Complexity

Metric	Value	Why
Time	`O(n log n)`	Each recursive level scans list segments to find middle nodes
Space	`O(log n)`	Recursion depth follows tree height

Here, n is the number of nodes in the linked list.

Finding the middle node costs linear time for each recursive segment.

Implementation

from typing import Optional

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        if head is None:
            return None

        if head.next is None:
            return TreeNode(head.val)

        prev = None
        slow = head
        fast = head

        while fast and fast.next:
            prev = slow
            slow = slow.next
            fast = fast.next.next

        prev.next = None

        root = TreeNode(slow.val)

        root.left = self.sortedListToBST(head)
        root.right = self.sortedListToBST(slow.next)

        return root

Code Explanation

The empty list case:

if head is None:
    return None

A single-node list becomes a leaf node:

if head.next is None:
    return TreeNode(head.val)

Initialize the pointers:

prev = None
slow = head
fast = head

The loop finds the middle node:

while fast and fast.next:
    prev = slow
    slow = slow.next
    fast = fast.next.next

slow moves one step.

fast moves two steps.

When the loop finishes:

slow

points to the middle node.

Disconnect the left half:

prev.next = None

Create the root node:

root = TreeNode(slow.val)

Build the left subtree from the left half:

root.left = self.sortedListToBST(head)

Build the right subtree from the nodes after the middle:

root.right = self.sortedListToBST(slow.next)

Finally:

return root

Testing

We can test correctness by checking:

The inorder traversal matches the original sorted values.
The tree is balanced.

from typing import Optional

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        if head is None:
            return None

        if head.next is None:
            return TreeNode(head.val)

        prev = None
        slow = head
        fast = head

        while fast and fast.next:
            prev = slow
            slow = slow.next
            fast = fast.next.next

        prev.next = None

        root = TreeNode(slow.val)

        root.left = self.sortedListToBST(head)
        root.right = self.sortedListToBST(slow.next)

        return root

def build_list(values):
    dummy = ListNode()
    cur = dummy

    for value in values:
        cur.next = ListNode(value)
        cur = cur.next

    return dummy.next

def inorder(root):
    if root is None:
        return []

    return inorder(root.left) + [root.val] + inorder(root.right)

def is_balanced(root):
    def height(node):
        if node is None:
            return 0

        left = height(node.left)
        right = height(node.right)

        if left == -1 or right == -1:
            return -1

        if abs(left - right) > 1:
            return -1

        return 1 + max(left, right)

    return height(root) != -1

def run_tests():
    s = Solution()

    values1 = [-10, -3, 0, 5, 9]
    root1 = s.sortedListToBST(build_list(values1))
    assert inorder(root1) == values1
    assert is_balanced(root1)

    values2 = [1, 3]
    root2 = s.sortedListToBST(build_list(values2))
    assert inorder(root2) == values2
    assert is_balanced(root2)

    values3 = [1]
    root3 = s.sortedListToBST(build_list(values3))
    assert inorder(root3) == values3
    assert is_balanced(root3)

    values4 = [-5, -2, 0, 1, 8, 10]
    root4 = s.sortedListToBST(build_list(values4))
    assert inorder(root4) == values4
    assert is_balanced(root4)

    print("all tests passed")

run_tests()

Test meaning:

Test	Why
`[-10,-3,0,5,9]`	Standard mixed values
`[1,3]`	Even-length list
`[1]`	Single-node tree
Larger sorted list	Confirms recursive splitting and balance