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 1:
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 shown height balanced BST.
Example 2:
Input: head = [] Output: []
Constraints:
head is in the range [0, 2 * 104].-105 <= Node.val <= 105In #109 Convert Sorted List to Binary Search Tree, the goal is to transform a sorted singly linked list into a height-balanced Binary Search Tree (BST). Because the list is already sorted, the key idea is to choose the middle element as the root so that the left and right subtrees remain balanced.
A common strategy uses the slow and fast pointer technique to locate the middle node of the linked list. The middle element becomes the root, while the left portion of the list forms the left subtree and the right portion forms the right subtree. This process is applied recursively using a divide and conquer approach.
An alternative and more optimized method simulates an in-order traversal while building the BST. By first computing the list length and recursively constructing subtrees, you can avoid repeatedly scanning the list.
The recursive divide-and-conquer approach typically runs in O(n log n) time due to repeated middle searches, while the in-order simulation can achieve O(n) time with O(log n) recursion stack space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Slow/Fast Pointer to Find Middle (Divide & Conquer) | O(n log n) | O(log n) |
| In-order Simulation with List Length | O(n) | O(log n) |
NeetCode
This approach involves converting the linked list to an array and then using the middle of the array to create a height-balanced binary search tree (BST). The middle of the array will become the root, and this concept is applied recursively to the left and right halves of the array.
Time Complexity: O(n), where n is the number of nodes in the linked list, because we traverse the list to create the array.
Space Complexity: O(n), for storing the values in the array.
1class ListNode:
2 def __init__(self, val=0, next=None):
3 self.val = val
4 self.next = next
5
6class TreeNode:
7 def __init__(self, val=0, left=None, right=None):
8 self.val = val
9 self.left = left
10 self.right = right
11
12class Solution:
13 def sortedListToBST(self, head: ListNode) -> TreeNode:
14 values = []
15 while head:
16 values.append(head.val)
17 head = head.next
18
19 def convertListToBST(left, right):
20 if left > right:
21 return None
22
23 mid = (left + right) // 2
24 node = TreeNode(values[mid])
25
26 if left == right:
27 return node
28
29 node.left = convertListToBST(left, mid - 1)
30 node.right = convertListToBST(mid + 1, right)
31 return node
32
33 return convertListToBST(0, len(values) - 1)The solution first converts the linked list into an array for easy access. It then uses the middle element of the array as the root of the BST and recursively applies this method to the left and right segments of the list. This way, a height-balanced BST is created.
This approach uses the slow and fast pointer technique to find the middle of the linked list, which forms the root of the BST. The linked list is recursively divided into two halves, and this method is used to create the left and right subtrees.
Time Complexity: O(n log n), because cutting the list in half at each step takes O(log n) splits, and each split involves a linear scan.
Space Complexity: O(log n), for the recursion stack where n is the number of nodes in the list.
1class ListNode {
2 int val;
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem or similar variations frequently appear in technical interviews at top tech companies. It tests understanding of linked lists, recursion, tree construction, and divide-and-conquer strategies.
The optimal approach simulates an in-order traversal while building the BST. By first calculating the linked list length and recursively constructing the tree, each node is processed exactly once, resulting in O(n) time complexity.
Choosing the middle element ensures the tree remains height-balanced. A balanced BST keeps operations like search, insertion, and deletion efficient by maintaining approximately equal subtree heights.
Understanding Binary Search Trees and linked list traversal is essential. The solution relies on selecting the middle element to maintain balance and using recursion or divide-and-conquer techniques to build the tree.
The Java solution uses a recursive function, with fast and slow pointers to find the middle of the linked list. This middle element becomes the root of the BST, and the process is applied to the list segments left and right of the middle to form the subtrees.