Solution Explanation

This problem asks to convert a sorted singly linked list into a height-balanced Binary Search Tree (BST). A height-balanced BST is a BST where the height of the left and right subtrees of any node differ by at most one.

The most efficient approach involves a divide-and-conquer strategy. We first convert the linked list into an array to allow for easy random access. This array is then used recursively to construct the BST.

Algorithm:

1. Convert Linked List to Array: Iterate through the linked list and store the values in an array. This step takes O(N) time, where N is the number of nodes in the linked list.

2. Recursive BST Construction: The core logic is a recursive function buildBST(nums, start, end):

   • Base Case: If start > end, it means we've reached the end of the subarray, so we return null (or None in Python).
   • Recursive Step:
     • Find the middle element mid = (start + end) // 2. This element will be the root of the current subtree.
     • Recursively call buildBST to construct the left subtree using the subarray from start to mid - 1.
     • Recursively call buildBST to construct the right subtree using the subarray from mid + 1 to end.
     • Create a new TreeNode with the value at nums[mid] as its value, the left subtree as its left child, and the right subtree as its right child.
     • Return the newly created TreeNode.

3. Return Root: The initial call to buildBST is made with the entire array (0 to len(nums)-1) to construct the complete BST. The function returns the root of the constructed BST.

Time Complexity Analysis:

• Converting the linked list to an array takes O(N) time.
• The buildBST function performs a binary divide-and-conquer approach, resulting in a logarithmic time complexity for each recursive call (O(log N)). Since we perform this for every element in the array of length N, the overall time complexity of the BST construction is O(N). This is because each node is visited and processed exactly once.

Space Complexity Analysis:

• The space complexity is dominated by the array used to store the linked list values and the recursive call stack.
• The array takes O(N) space.
• The recursion depth of the buildBST function is O(log N) in the average case (for a balanced tree) and O(N) in the worst case (for a skewed tree). However, the overall space complexity is O(N) due to the array.

Code Examples (Python):

The Python code directly implements this algorithm:

class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        nums = []
        while head:
            nums.append(head.val)
            head = head.next
 
        def buildBST(nums, start, end):
            if start > end:
                return None
            mid = (start + end) // 2
            root = TreeNode(nums[mid])
            root.left = buildBST(nums, start, mid - 1)
            root.right = buildBST(nums, mid + 1, end)
            return root
 
        return buildBST(nums, 0, len(nums) - 1)
 

The other languages follow a very similar structure, differing only in syntax. They all achieve the same time and space complexity.