LeetCode 109 - Convert Sorted List to Binary Search Tree

LeetCode Problem 109

Difficulty: 🟡 Medium
Topics: Linked List, Divide and Conquer, Tree, Binary Search Tree, Binary Tree

Solution

Problem Understanding

The problem gives us the head of a singly linked list whose values are already sorted in ascending order. We must convert this linked list into a height balanced Binary Search Tree, usually abbreviated as BST.

A Binary Search Tree has the property that:

• Every node in the left subtree contains values smaller than the current node.
• Every node in the right subtree contains values larger than the current node.

A height balanced tree means that for every node, the heights of the left and right subtrees differ by at most one. This requirement is important because balanced trees provide efficient lookup performance.

The linked list is sorted, which is the key observation. If we repeatedly choose the middle element of a sorted sequence as the root, then:

• All values before the middle naturally belong to the left subtree.
• All values after the middle naturally belong to the right subtree.
• The resulting tree remains balanced because the left and right halves are roughly equal in size.

The input is a singly linked list, not an array. That distinction matters because linked lists do not support random access. Accessing the middle element requires traversal.

The constraints tell us that the list can contain up to 2 * 10^4 nodes. An O(n^2) solution could become too slow in the worst case, so we should aim for something closer to O(n log n) or ideally O(n).

Several edge cases are important:

• The list may be empty.
• The list may contain only one node.
• The list may contain two nodes, which can create imbalance bugs if splitting is handled incorrectly.
• Because the list is singly linked, we must be careful when cutting the list into halves.
• Duplicate balancing mistakes can create skewed trees rather than height balanced ones.

Approaches

Brute Force Approach

A straightforward idea is to first copy all linked list values into an array.

Since arrays support random access, we can then recursively construct the BST exactly like the classic "sorted array to BST" problem:

1. Choose the middle element as the root.
2. Recursively build the left subtree from the left half.
3. Recursively build the right subtree from the right half.

This works because the array remains sorted, and selecting the middle element guarantees balance.

The downside is that we must allocate an additional array containing all values. While this approach is already efficient enough for the constraints, it does not fully leverage the linked list structure.

Optimal Approach

The better approach avoids converting the list into an array.

The key insight is that an inorder traversal of a BST visits nodes in sorted order. Since the linked list is already sorted, we can simulate inorder construction directly from the list.

The process works like this:

1. Compute the total number of nodes in the linked list.
2. Recursively construct the BST using index boundaries.
3. Build the left subtree first.
4. Use the current linked list node as the root.
5. Advance the linked list pointer.
6. Build the right subtree.

This technique ensures that nodes are consumed from the linked list in sorted order, exactly matching inorder traversal order.

Because every linked list node is visited exactly once, the solution runs in linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Convert linked list to array, then build BST recursively
Optimal	O(n)	O(log n)	Simulate inorder traversal directly on the linked list

Algorithm Walkthrough

Optimal Inorder Simulation Algorithm

1. First, traverse the linked list once to count how many nodes exist.

We need the size because our recursive function will build the BST using index ranges rather than physically splitting the list. 2. Store the linked list head in a shared pointer variable.

This pointer represents the current node that should become the next BST node during inorder construction. 3. Define a recursive function build(left, right).

This function constructs a balanced BST using the conceptual subarray range from left to right. 4. If left > right, return None.

This is the base case indicating that the subtree is empty. 5. Compute the middle index.

The middle element should become the root to maintain balance. 6. Recursively build the left subtree first.

This is critical because inorder traversal processes nodes in the order:

• left subtree
• root
• right subtree

7. After the left subtree is built, the shared linked list pointer now points to the correct root value.

Create a tree node using this linked list node. 8. Advance the linked list pointer to the next node.

This prepares the pointer for constructing the right subtree. 9. Recursively build the right subtree. 10. Attach the left and right children to the root and return the root node.

Why it works

The algorithm works because it exactly mirrors inorder traversal.

During inorder traversal of a BST:

• Left subtree nodes are processed first.
• Then the root.
• Then the right subtree.

Since the linked list is already sorted, consuming nodes sequentially from the list naturally matches inorder order. The recursive boundaries ensure that the middle element of each segment becomes the subtree root, which guarantees height balance.

Python Solution

# 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]:
        def get_size(node: Optional[ListNode]) -> int:
            size = 0
            
            while node:
                size += 1
                node = node.next
            
            return size
        
        size = get_size(head)
        current = head
        
        def build(left: int, right: int) -> Optional[TreeNode]:
            nonlocal current
            
            if left > right:
                return None
            
            mid = (left + right) // 2
            
            left_subtree = build(left, mid - 1)
            
            root = TreeNode(current.val)
            root.left = left_subtree
            
            current = current.next
            
            root.right = build(mid + 1, right)
            
            return root
        
        return build(0, size - 1)

The implementation starts by computing the size of the linked list. This allows the recursive builder to operate on index ranges rather than repeatedly searching for middle nodes.

The current pointer tracks which linked list node should become the next BST node during inorder construction.

The recursive build() function constructs the BST exactly as an inorder traversal would visit it. First it builds the left subtree, then creates the current root node using the linked list pointer, then advances the pointer, and finally constructs the right subtree.

Because the linked list pointer moves forward exactly once per node, every list node is processed a single time.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func sortedListToBST(head *ListNode) *TreeNode {
    size := getSize(head)
    current := head

    var build func(left int, right int) *TreeNode

    build = func(left int, right int) *TreeNode {
        if left > right {
            return nil
        }

        mid := (left + right) / 2

        leftSubtree := build(left, mid-1)

        root := &TreeNode{
            Val: current.Val,
        }

        root.Left = leftSubtree

        current = current.Next

        root.Right = build(mid+1, right)

        return root
    }

    return build(0, size-1)
}

func getSize(head *ListNode) int {
    size := 0

    for head != nil {
        size++
        head = head.Next
    }

    return size
}

The Go implementation follows the same inorder simulation strategy as the Python version.

Instead of Python's nonlocal keyword, Go closures naturally capture the current pointer variable from the outer scope.

Go uses nil instead of None, and tree nodes are created using pointer allocation with &TreeNode{}.

Worked Examples

Example 1

Input:

[-10, -3, 0, 5, 9]

Step 1: Count Nodes

Node	Count
-10	1
-3	2
0	3
5	4
9	5

Total size = 5

We now call:

build(0, 4)

Step 2: Build Root

Left	Right	Mid
0	4	2

Index 2 becomes the root position.

But before creating the root, we must build the left subtree.

Step 3: Build Left Subtree

Call:

build(0, 1)

Left	Right	Mid
0	1	0

Again, build the left subtree first:

build(0, -1)

This returns None.

Now current list node is -10.

Create:

TreeNode(-10)

Advance current pointer to -3.

Now build right subtree:

build(1, 1)

Create node -3.

The left subtree becomes:

   -10
      \
      -3

Step 4: Create Root

After the left subtree finishes, current pointer is now at 0.

Create:

TreeNode(0)

Advance current pointer to 5.

Step 5: Build Right Subtree

Call:

build(3, 4)

Mid becomes 3.

Create node 5.

Advance current pointer to 9.

Then create node 9.

Final tree:

       0
     /   \
   -10    5
      \     \
      -3     9

This is height balanced.

Example 2

Input:

[]

Size becomes 0.

Initial call:

build(0, -1)

Since left > right, return None.

Final output:

[]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each linked list node is visited exactly once
Space	O(log n)	Recursive call stack depth for balanced BST construction

The algorithm performs one pass to count nodes and one recursive inorder construction pass. No node is revisited, so the total runtime is linear.

The recursive stack depth corresponds to the height of the balanced BST. Since the tree is balanced, the height is logarithmic.

Test Cases

from collections import deque

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):
        def get_size(node):
            size = 0

            while node:
                size += 1
                node = node.next

            return size

        size = get_size(head)
        current = head

        def build(left, right):
            nonlocal current

            if left > right:
                return None

            mid = (left + right) // 2

            left_subtree = build(left, mid - 1)

            root = TreeNode(current.val)
            root.left = left_subtree

            current = current.next

            root.right = build(mid + 1, right)

            return root

        return build(0, size - 1)

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

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

    return dummy.next

def inorder(root):
    if not root:
        return []

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

solution = Solution()

# Empty list
root = solution.sortedListToBST(build_list([]))
assert root is None  # tests empty input

# Single node
root = solution.sortedListToBST(build_list([1]))
assert inorder(root) == [1]  # tests single element

# Two nodes
root = solution.sortedListToBST(build_list([1, 2]))
assert inorder(root) == [1, 2]  # tests minimal non-trivial tree

# Odd number of nodes
root = solution.sortedListToBST(build_list([-10, -3, 0, 5, 9]))
assert inorder(root) == [-10, -3, 0, 5, 9]  # tests standard example

# Even number of nodes
root = solution.sortedListToBST(build_list([1, 2, 3, 4]))
assert inorder(root) == [1, 2, 3, 4]  # tests balanced construction

# Negative values
root = solution.sortedListToBST(build_list([-5, -4, -3, -2, -1]))
assert inorder(root) == [-5, -4, -3, -2, -1]  # tests negative numbers

# Duplicate values
root = solution.sortedListToBST(build_list([1, 1, 1, 1]))
assert inorder(root) == [1, 1, 1, 1]  # tests duplicates

# Larger input
values = list(range(100))
root = solution.sortedListToBST(build_list(values))
assert inorder(root) == values  # tests larger balanced tree

Test	Why
Empty list	Validates base case handling
Single node	Ensures one-node tree creation works
Two nodes	Tests smallest meaningful split
Odd number of nodes	Verifies balanced middle selection
Even number of nodes	Ensures balanced construction with even sizes
Negative values	Confirms ordering works with negatives
Duplicate values	Verifies duplicates are handled correctly
Larger input	Stress tests recursion and correctness

Edge Cases

Empty Linked List

An empty linked list is the simplest edge case. A naive implementation might attempt to access head.val without checking whether the list exists. This implementation handles the case safely because the size becomes zero, and the recursive call immediately returns None.

Single Node List

A list containing exactly one node can expose incorrect recursion boundaries. If the midpoint logic is wrong, recursive calls may never terminate properly. In this implementation, the range becomes (0, 0), producing exactly one root node with no children.

Two Node List

Two-node inputs are particularly tricky for balancing logic. Some implementations accidentally reuse nodes or create skewed recursion. Here, midpoint selection ensures one node becomes the root and the other becomes a child, maintaining BST ordering and avoiding infinite recursion.

Large Linked List

With up to 2 * 10^4 nodes, repeatedly searching for middle nodes would create excessive overhead. The inorder simulation approach avoids repeated traversal and guarantees linear runtime, making it scalable for the maximum constraint size.