Problem Description

You are given the head of a singly linked list where elements are sorted in ascending order. Your task is to convert this sorted linked list into a height-balanced binary search tree (BST).

A height-balanced binary search tree is a binary tree where:

• The left subtree of every node contains only nodes with values less than the node's value
• The right subtree of every node contains only nodes with values greater than the node's value
• The depth of the two subtrees of every node never differs by more than 1

For example, if you have a sorted linked list like 1 -> 2 -> 3 -> 4 -> 5, you need to construct a balanced BST where the middle element becomes the root, and the elements are distributed evenly between left and right subtrees to maintain balance.

The solution approach converts the linked list to an array first, making it easier to access middle elements. Then it uses a divide-and-conquer strategy with depth-first search (DFS) to build the tree. The function dfs(i, j) recursively:

• Finds the middle index mid of the current range [i, j]
• Creates a root node with value nums[mid]
• Recursively builds the left subtree from range [i, mid-1]
• Recursively builds the right subtree from range [mid+1, j]
• Returns the constructed subtree rooted at mid

The bit shift operation (i + j) >> 1 is used to calculate the middle index, which is equivalent to (i + j) // 2 but more efficient.

Intuition

When building a height-balanced BST from a sorted sequence, the key insight is that we need to choose the middle element as the root to ensure balance. This is because if we pick the middle element, we'll have roughly equal numbers of elements on both sides, which can form balanced left and right subtrees.

Think about it this way: if we have a sorted array [1, 2, 3, 4, 5], choosing 3 as the root gives us [1, 2] for the left subtree and [4, 5] for the right subtree. This naturally creates a balanced structure.

The challenge with a linked list is that we can't directly access the middle element in O(1) time like we can with an array. We could use the two-pointer technique (slow and fast pointers) to find the middle of the linked list each time, but this would be inefficient since we'd need to traverse the list multiple times during the recursive construction.

This leads us to a practical trade-off: convert the linked list to an array first. Yes, this requires O(n) extra space, but it allows us to access any element by index in O(1) time. Once we have the array, we can efficiently apply the divide-and-conquer approach:

1. Find the middle index: mid = (i + j) // 2
2. Use nums[mid] as the root value
3. Recursively build the left subtree from the left half [i, mid-1]
4. Recursively build the right subtree from the right half [mid+1, j]

This recursive pattern naturally maintains the BST property (left < root < right) because our original list is sorted, and it maintains balance because we're always splitting the remaining elements roughly in half. The recursion handles all the subtree construction automatically, making the solution elegant and straightforward.

Solution Approach

The implementation uses a two-phase approach: first converting the linked list to an array, then using DFS to construct the balanced BST.

Phase 1: Convert Linked List to Array

nums = []
while head:
    nums.append(head.val)
    head = head.next

We traverse the linked list once, storing all values in an array nums. This takes O(n) time and O(n) space, but gives us random access to elements which is crucial for the next phase.

Phase 2: Construct BST using DFS

The core of the solution is the recursive dfs function:

def dfs(i: int, j: int) -> Optional[TreeNode]:
    if i > j:
        return None
    mid = (i + j) >> 1
    l, r = dfs(i, mid - 1), dfs(mid + 1, j)
    return TreeNode(nums[mid], l, r)

Let's break down how this works:

1. Base Case: When i > j, we've exhausted the current range, so we return None to indicate no node exists here.

2. Find Middle: We calculate mid = (i + j) >> 1. The bit shift operation >> 1 is equivalent to integer division by 2, giving us the middle index of the current range.

3. Recursive Construction:

   • First, we recursively build the left subtree from range [i, mid - 1]
   • Then, we recursively build the right subtree from range [mid + 1, j]
   • Notice the order here - we build both subtrees before creating the current node

4. Create Current Node: We create a new TreeNode with value nums[mid], attaching the previously constructed left and right subtrees.

Example Walkthrough

For array [1, 2, 3, 4, 5] (indices 0-4):

• Initial call: dfs(0, 4), mid = 2, creates node with value 3
  • Left recursive call: dfs(0, 1), mid = 0, creates node with value 1
    • Left: dfs(0, -1) returns None
    • Right: dfs(1, 1), mid = 1, creates node with value 2
  • Right recursive call: dfs(3, 4), mid = 3, creates node with value 4
    • Left: dfs(3, 2) returns None
    • Right: dfs(4, 4), mid = 4, creates node with value 5

The final call dfs(0, len(nums) - 1) returns the root of the complete balanced BST.

This divide-and-conquer pattern ensures that at each level, we're splitting the remaining elements roughly in half, maintaining the height-balanced property throughout the tree construction.

Example Walkthrough

Let's walk through converting the sorted linked list 1 -> 2 -> 3 to a height-balanced BST.

Step 1: Convert Linked List to Array

• Traverse the linked list: 1 -> 2 -> 3
• Create array: nums = [1, 2, 3] (indices 0, 1, 2)

Step 2: Build BST using DFS

We'll trace through the recursive calls:

Initial Call: dfs(0, 2)

• Calculate mid: (0 + 2) >> 1 = 1
• This will create root node with value nums[1] = 2
• But first, we need to build left and right subtrees

Left Subtree: dfs(0, 0)

• Calculate mid: (0 + 0) >> 1 = 0
• Create node with value nums[0] = 1
• Check left child: dfs(0, -1) → returns None (base case: 0 > -1)
• Check right child: dfs(1, 0) → returns None (base case: 1 > 0)
• Return node 1 with no children

Right Subtree: dfs(2, 2)

• Calculate mid: (2 + 2) >> 1 = 2
• Create node with value nums[2] = 3
• Check left child: dfs(2, 1) → returns None (base case: 2 > 1)
• Check right child: dfs(3, 2) → returns None (base case: 3 > 2)
• Return node 3 with no children

Final Assembly:

• Create root node with value 2
• Attach left child: node 1
• Attach right child: node 3

Result:

    2
   / \
  1   3

The tree is perfectly balanced with height difference of 0 between left and right subtrees, and maintains the BST property where left (1) < root (2) < right (3).

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm consists of two main phases:

1. Converting the linked list to an array: This requires traversing the entire linked list once, taking O(n) time where n is the number of nodes in the linked list.
2. Building the BST recursively: The dfs function visits each element in the array exactly once to create a corresponding TreeNode. Although the recursion follows a divide-and-conquer pattern similar to merge sort, each element is processed only once, resulting in O(n) time.

Therefore, the total time complexity is O(n) + O(n) = O(n).

Space Complexity: O(n)

The space complexity consists of:

1. The nums array that stores all values from the linked list: O(n) space.
2. The output BST which contains n TreeNode objects: O(n) space.
3. The recursion call stack: In the worst case, the recursion depth is O(log n) for a balanced tree construction.

Since O(n) + O(n) + O(log n) = O(n), the total space complexity is O(n).

Common Pitfalls

1. Inefficient Middle Element Access in Linked List

The Pitfall: A common mistake is trying to find the middle element directly in the linked list without converting it to an array first. This leads to repeatedly traversing the linked list to find middle elements during recursion.

# Inefficient approach - DON'T DO THIS
def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
    def findMiddle(start, end):
        slow = fast = start
        prev = None
        while fast != end and fast.next != end:
            prev = slow
            slow = slow.next
            fast = fast.next.next
        return slow, prev
  
    def buildBST(start, end):
        if start == end:
            return None
        mid, prev = findMiddle(start, end)
        root = TreeNode(mid.val)
        root.left = buildBST(start, mid)
        root.right = buildBST(mid.next, end)
        return root
  
    return buildBST(head, None)

Why it's problematic: This approach has O(n log n) time complexity because finding the middle element takes O(n) time, and we do this for every recursive call. The total number of recursive calls is O(n), leading to overall O(n log n) complexity.

Solution: Convert the linked list to an array first (as shown in the correct implementation). This gives O(1) access to any element by index, reducing the overall time complexity to O(n).

2. Integer Overflow in Middle Calculation

The Pitfall: When calculating the middle index, using mid = (left + right) // 2 can cause integer overflow in languages with fixed integer sizes (though Python handles big integers automatically).

# Potential overflow in other languages
mid = (left + right) // 2  # Could overflow if left + right > MAX_INT

Solution: Use either of these alternatives:

# Method 1: Bit shift (shown in original solution)
mid = (left + right) >> 1

# Method 2: Avoid overflow explicitly
mid = left + (right - left) // 2

3. Modifying the Original Linked List

The Pitfall: Some implementations might try to modify the original linked list structure during traversal, breaking the list for future use.

# BAD: Modifying the original list
def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
    values = []
    while head:
        values.append(head.val)
        temp = head
        head = head.next
        temp.next = None  # DON'T DO THIS - destroys the original list
    # ... rest of the code

Solution: Simply traverse the list without modifying it:

# GOOD: Preserve the original list
current = head
while current:
    values.append(current.val)
    current = current.next

4. Off-by-One Errors in Recursion Boundaries

The Pitfall: Incorrectly handling the recursion boundaries, especially mixing inclusive and exclusive ranges.

# WRONG: Inconsistent boundary handling
def build_bst(left: int, right: int) -> Optional[TreeNode]:
    if left >= right:  # Wrong condition for inclusive boundaries
        return None
    mid = (left + right) // 2
    left_subtree = build_bst(left, mid)  # Should be mid - 1
    right_subtree = build_bst(mid + 1, right)
    # ...

Solution: Be consistent with inclusive boundaries:

# CORRECT: Consistent inclusive boundaries
def build_bst(left: int, right: int) -> Optional[TreeNode]:
    if left > right:  # Correct condition for inclusive boundaries
        return None
    mid = (left + right) // 2
    left_subtree = build_bst(left, mid - 1)  # Exclusive of mid
    right_subtree = build_bst(mid + 1, right)  # Exclusive of mid
    # ...

5. Not Handling Edge Cases

The Pitfall: Forgetting to handle empty lists or single-node lists properly.

Solution: The base case if left > right: return None naturally handles these edge cases:

• Empty list: build_bst(0, -1) returns None
• Single node: build_bst(0, 0) creates one node with both children as None