LeetCode 109: Convert Sorted List to Binary Search Tree Solution in Python Explained

Problem Statement

In LeetCode 109, you’re given the head of a singly linked list sorted in ascending order. Your task is to convert it into a height-balanced BST and return its root, ensuring the depth difference between left and right subtrees is at most 1 for every node. This builds on LeetCode 108: Convert Sorted Array to Binary Search Tree, adapting from an array to a linked list, and differs from level-order traversal like LeetCode 107: Binary Tree Level Order Traversal II.

Constraints

• Number of nodes: 0 <= n <= 2 * 10^4
• Node values: -10^5 <= Node.val <= 10^5
• List is sorted in ascending order

Example

Let’s see some cases:

Copy codeInput: head = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5] or similar
      0
     / \
   -3   9
   /   /
 -10  5
Explanation: Height-balanced BST, e.g., root 0, left [-10,-3], right [5,9].

Copy codeInput: head = [1,3]
Output: [3,1] or [1,null,3]
      3    or    1
     /          \
    1            3
Explanation: Either is valid, balanced with depth difference ≤ 1.

Copy codeInput: head = []
Output: null
Explanation: Empty list, no tree.

These examples show we’re building a balanced BST from a sorted linked list.

Understanding the Problem

How do you solve LeetCode 109: Convert Sorted List to Binary Search Tree in Python? Take head = [-10,-3,0,5,9]. We need a height-balanced BST, like [0,-3,9,-10,null,5]—root at the midpoint (0), left subtree [-10,-3], right subtree [5,9]. The sorted order ensures BST properties (left < root < right), but unlike an array, we can’t directly index the list. This isn’t a depth calculation like LeetCode 104: Maximum Depth of Binary Tree; it’s about balanced BST construction from a linked list. We’ll use: 1. Recursive Midpoint with Slow-Fast Pointer: O(n) time, O(h) space—our best solution. 2. Array Conversion with Midpoint Division: O(n) time, O(n) space—an alternative.

Let’s dive into the best solution.

Best Solution: Recursive Midpoint with Slow-Fast Pointer Approach

Explanation

Recursive Midpoint with Slow-Fast Pointer constructs a height-balanced BST by finding the midpoint of the linked list using the slow-fast pointer technique (to split without counting), making it the root, and recursively building left and right subtrees. The head pointer advances with recursion to process sublists. This is the best solution due to its O(n) time complexity, minimal space usage (no extra array), and elegant use of linked list properties to achieve balance.

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

• Midpoint: 0 (slow pointer), Left: [-10,-3], Right: [5,9].
• Left mid: -3, Left: [-10], Right: [].
• Right mid: 9, Left: [5], Right: [].
• Result: [0,-3,9,-10,null,5].

Step-by-Step Example

Assume classes: class ListNode: def __init__(self, val=0, next=None): self.val = val; self.next = next and class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val; self.left = left; self.right = right.

Example 1: head = [-10,-3,0,5,9]

Goal: Return [0,-3,9,-10,null,5] or similar balanced BST.

• Start: self.head = -10, sortedListToBST(5).
• Step 1: Size = 5, slow = -10, fast = 0, mid = 0.
• Left size = 2, Left: sortedListToBST(2).
• slow = -10, fast = 0, mid = -3.
• Left: sortedListToBST(1) → -10.
• Right: sortedListToBST(0) → None.
• Return -3->-10.
• Advance self.head to 5, Right: sortedListToBST(2).
• slow = 5, fast = None, mid = 9.
• Left: sortedListToBST(1) → 5.
• Right: sortedListToBST(0) → None.
• Return 9->5.
• Return 0->-3->9.
• Finish: [0,-3,9,-10,null,5].

Example 2: head = [1,3]

Goal: Return [3,1] or [1,null,3].

• Start: self.head = 1, sortedListToBST(2).
• Step 1: slow = 1, fast = None, mid = 3.
• Left: sortedListToBST(1) → 1.
• Right: sortedListToBST(0) → None.
• Finish: [3,1].

Example 3: head = []

Goal: Return null.

• Start: sortedListToBST(0).
• Step 1: Size = 0, return None.
• Finish: Return null.

How the Code Works (Recursive Midpoint with Slow-Fast Pointer) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codeclass 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 __init__(self):
        self.head = None

    def sortedListToBST(self, head: ListNode) -> TreeNode:
        # Line 1: Set global head pointer
        self.head = head
        # Initializes head for tracking (e.g., -10)

        # Line 2: Calculate list length
        size = 0
        curr = head
        while curr:
            size += 1
            curr = curr.next
        # Counts nodes (e.g., 5 for [-10,-3,0,5,9])

        # Line 3: Define recursive builder function
        def build(size: int) -> TreeNode:
            # size = number of nodes in current segment (e.g., 5)

            # Line 4: Base case - no nodes
            if size == 0:
                # If size is 0 (e.g., empty segment), return None
                return None

            # Line 5: Find midpoint using slow-fast pointer
            slow = fast = self.head
            for _ in range(size // 2):
                fast = fast.next.next if fast.next else fast.next
                slow = slow.next
            # Slow reaches mid (e.g., 0), fast reaches end or near-end

            # Line 6: Create root node with midpoint value
            root = TreeNode(slow.val)
            # Midpoint as root (e.g., 0)

            # Line 7: Calculate left subtree size
            left_size = (size - 1) // 2
            # Nodes before mid (e.g., 2 for [-10,-3])

            # Line 8: Build left subtree
            root.left = build(left_size)
            # Recursively builds left (e.g., [-10,-3] → -3->-10)

            # Line 9: Advance head pointer past midpoint
            self.head = slow.next
            # Moves to next segment (e.g., 5 after 0)

            # Line 10: Build right subtree
            root.right = build(size - left_size - 1)
            # Recursively builds right (e.g., [5,9] → 9->5)

            # Line 11: Return constructed subtree
            return root
            # Returns root of current subtree (e.g., 0->-3->9)

        # Line 12: Start construction
        return build(size)
        # Initiates with full size (e.g., 5)
        # Returns root of balanced BST

# Example usage:
# head = ListNode(-10)
# head.next = ListNode(-3)
# head.next.next = ListNode(0)
# head.next.next.next = ListNode(5)
# head.next.next.next.next = ListNode(9)
# solution = Solution()
# result = solution.sortedListToBST(head)

This detailed breakdown clarifies how recursive midpoint division with a slow-fast pointer efficiently constructs a height-balanced BST.

Alternative: Array Conversion with Midpoint Division Approach

Explanation

Array Conversion with Midpoint Division converts the linked list to an array first, then uses the same midpoint division as LeetCode 108 to build the BST. It’s a practical alternative, simplifying the process by leveraging array indexing, but uses O(n) extra space.

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

• Array: [-10,-3,0,5,9].
• Mid: 0, Left: [-10,-3], Right: [5,9].
• Result: [0,-3,9,-10,null,5].

Step-by-Step Example (Alternative)

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

• Step 1: Convert to array [-10,-3,0,5,9].
• Step 2: build(0, 5).
• Mid = 2, Root = 0.
• Left: build(0, 2) → -3->-10.
• Right: build(3, 5) → 9->5.
• Finish: [0,-3,9,-10,null,5].

How the Code Works (Array Conversion)

Copy codedef sortedListToBSTArray(head: ListNode) -> TreeNode:
    # Convert list to array
    nums = []
    curr = head
    while curr:
        nums.append(curr.val)
        curr = curr.next

    def build(start: int, end: int) -> TreeNode:
        if start >= end:
            return None
        mid = (start + end) // 2
        root = TreeNode(nums[mid])
        root.left = build(start, mid)
        root.right = build(mid + 1, end)
        return root

    return build(0, len(nums))

Complexity

• Recursive Midpoint with Slow-Fast Pointer:
• Time: O(n) – visits each node once.
• Space: O(h) – recursion stack, h = height.
• Array Conversion with Midpoint Division:
• Time: O(n) – array conversion and tree building.
• Space: O(n) – array storage.

Efficiency Notes

Recursive Midpoint with Slow-Fast Pointer is the best solution with O(n) time and O(h) space, avoiding extra array space—Array Conversion with Midpoint Division matches time complexity but uses O(n) space, making it a simpler but less space-efficient alternative.

Key Insights

• Midpoint: Ensures balance.
• Slow-Fast: Finds midpoint in list.
• Sorted Order: Guarantees BST properties.

Additional Example

For head = [1,2,3,4]:

• Goal: [2,1,3,null,4] or similar.
• Slow-Fast: Mid = 2, Left: [1], Right: [3,4].

Edge Cases

• Empty List: [] → None.
• Single Node: [1] → [1].
• Two Nodes: [1,2] → [1,null,2].

Both solutions handle these well.

Final Thoughts

LeetCode 109: Convert Sorted List to Binary Search Tree in Python is a clever BST construction challenge. The Recursive Midpoint with Slow-Fast Pointer solution excels with its efficiency and elegance, while Array Conversion with Midpoint Division offers a familiar array-based approach. Want more? Try LeetCode 108: Convert Sorted Array to Binary Search Tree for the array version or LeetCode 94: Binary Tree Inorder Traversal for traversal basics. Ready to practice? Solve LeetCode 109 on LeetCode with [-10,-3,0,5,9], aiming for [0,-3,9,-10,null,5]—test your skills now!