algoadvance

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

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Example:

Input: head = [-10, -3, 0, 5, 9]
Output: [0, -3, 9, -10, null, 5]
Explanation: One possible answer is [0, -3, 9, -10, null, 5], which represents the following height balanced BST:
      0
     / \
   -3   9
   /   /
 -10  5

Constraints:

• The number of nodes in head is in the range [0, 2 * 10^4].
• -10^5 <= Node.val <= 10^5

Clarifying Questions

1. Q: How to handle when the input list is empty? A: Return None since an empty list cannot form a tree.

2. Q: Do we need to maintain the order of the input list? A: The values need to be in the same relative order, but the structure will change to satisfy BST properties.

3. Q: Can we assume the values and the structure of the input linked list are valid? A: Yes, we can assume the input is valid and sorted.

Strategy

1. Convert the List to an Array:
   • Traverse the linked list and store the values in an array. This allows O(1) time access to elements which is useful for constructing the BST.
2. Recursively Build the Tree:
   • Use recursion to split the array into two halves.
   • The middle element of the current array (or subarray) becomes the root of the current subtree.
   • Recursively build the left subtree using the left half of the array and the right subtree using the right half.

Steps:

1. Define the base case for the recursion.
2. Recursively determine the middle element of the current segment of the array.
3. Set that middle element as the root.
4. Recursively construct the left and right subtrees.

Code

Here is the Python implementation for the problem:

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

def sortedListToBST(head: ListNode) -> TreeNode:
    # Helper function to convert linked list to array
    def list_to_array(head):
        array = []
        while head:
            array.append(head.val)
            head = head.next
        return array
    
    # Helper function to convert sorted array to BST
    def sorted_array_to_bst(nums, left, right):
        if left > right:
            return None
        mid = (left + right) // 2
        node = TreeNode(nums[mid])
        node.left = sorted_array_to_bst(nums, left, mid - 1)
        node.right = sorted_array_to_bst(nums, mid + 1, right)
        return node
    
    nums = list_to_array(head)
    return sorted_array_to_bst(nums, 0, len(nums) - 1)

Time Complexity

• Time complexity: O(N), where N is the number of nodes in the linked list. We traverse the list once to convert it into an array (O(N)) and then construct the BST in O(N) time.
• Space complexity: O(N) for storing the array and the call stack during recursion.

This approach ensures we efficiently convert the sorted linked list into a height-balanced binary search tree.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?