Convert Sorted List To Binary Search Tree

Problem

• Given the head of a singly linked list where elements are sorted in ascending order, convert it to a height-balanced binary search tree.

Example:

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

Output: [0,-3,9,-10,null,5]

Approach

• 1. Convert the linked list into an array so that elements can be accessed in O(1) time. Then use a divide-and-conquer strategy: recursively pick the middle element as the root, and apply the same logic to the left and right subarrays.
• 2. This simplifies pointer logic compared to working directly with the list, at the cost of extra space. The split-and-recursively-build logic mirrors the classic sorted array to BST pattern.

Edge Cases

• [] → nil

Reflections

This was my first medium-level problem, and it felt like a solid step up from the easier problems. Having solved 108 recently helped because the approach.

I'm not proud of the performance, beating only 22% on time and 20% on memory. But the extra conversion step from linked list to array paid off in simplicity during the tree construction phase.

I have no doubt there is a version of this that is possible with a slow and fast pointer on the linked list, and I'll try it at some point.

Go Solution

func sortedListToBST(head *ListNode) *TreeNode {
    nums := linkedListToArray(head)
    if len(nums) == 0 {
        return nil
    }

    if len(nums) == 1 {
        return &TreeNode{Val:nums[0]}
    }
    
    mid := len(nums)/2

    node := &TreeNode{Val:nums[mid]}

    leftArr := nums[:mid]
    rightArr := nums[mid+1:]

    node.Left = insert(leftArr)
    node.Right = insert(rightArr)

    return node
}

func insert(nums []int) *TreeNode {
     if len(nums) == 0 {
        return nil
    }

    if len(nums) == 1 {
        return &TreeNode{Val:nums[0]}
    }
 
    mid := len(nums)/2

    node := &TreeNode{Val:nums[mid]}

    leftArr := nums[:mid]
    rightArr := nums[mid+1:]

    node.Left = insert(leftArr)
    node.Right = insert(rightArr)

    return node

}

func linkedListToArray(node *ListNode) []int {
    var nums []int

    for node != nil {
        nums = append(nums,node.Val)
        node = node.Next    
    }

    return nums
}

Performance

• Runtime beats: 21.92%
• Memory beats: 20.55%

Complexity

• Time: O(n) You convert the linked list to an array in O(n), then recursively build the BST by visiting each element once. Total work done across all recursive calls is linear.
• Space: O(n) O(n) to store the array converted from the linked list, plus O(log n) recursion stack space. Tree nodes also use O(n) memory, which is required output space.