Convert Sorted List to Binary Search Tree
Problem Description
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:
- The number of nodes in
headis in the range [0, 2 * 104]. - -105 <= Node.val <= 105
Solve it on LeetCode
Approaches
1. Naive Approach: Convert List to Array
Intuition:
The simplest way to address this problem is to transform the sorted linked list into an array. Once in array form, the middle element of any subarray serves as the root for the Binary Search Tree (BST). By recursively applying this process to the left and right subarrays, we build the complete tree.
This method is straightforward as it leverages the property of arrays that allow O(1) element access. However, this comes with a storage cost since we need additional space for the array.
Steps:
- Convert the linked list into an array.
- Recursively build BST from the array’s middle elements:
- Choose the middle of the current array segment as the root.
- Recursively create left and right subtrees using the subarrays to the left and right of the middle element.
Code:
- Time Complexity: O(N), where N is the number of elements in the list. Converting the list to an array takes O(N), and creating the BST takes O(N) as each element is processed once.
- Space Complexity: O(N), due to the additional space required to store the array.
2. Optimized Approach: Inorder Simulation
Intuition:
Instead of first converting the linked list to an array, we can directly use the properties of the list and simulate an inorder traversal. By using the fast and slow pointer technique, we can find the middle element of the linked list and use it as the root. This method eliminates the need for extra space associated with array storage.
Steps:
- Use a helper function to recursively find and set the middle element of the list as the root.
- Use two pointers (fast and slow) to find the middle:
- Move
fasttwo steps andslowone step to maintain the alignment needed to find the middle. - Recursively apply the same process to the left and right sublists.
Code:
- Time Complexity: O(N log N), each node is processed in O(log N) time and each call to find the middle takes linear time across all levels of the recursive tree.
- Space Complexity: O(log N), due to the recursion stack used during the divide process.