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 <= 105Problem Overview: You receive the head of a sorted singly linked list and must convert it into a height-balanced binary search tree. The BST property must hold (left < root < right) while keeping the tree balanced so operations remain efficient.
Approach 1: Convert Linked List to Array (O(n) time, O(n) space)
The simplest strategy is to copy the linked list values into an array. Once stored in an array, the problem becomes identical to building a balanced BST from a sorted array. Recursively choose the middle index as the root, build the left subtree from the left half, and the right subtree from the right half. Array indexing gives constant-time access to the middle element, so the recursion runs in O(n) time with O(n) extra space for the array. This approach is easy to reason about and often preferred when clarity matters more than strict memory usage.
Approach 2: Fast and Slow Pointer (O(n log n) time, O(log n) space)
This approach avoids converting the list into an array. Use the classic fast and slow pointer technique to locate the middle node of the linked list, which becomes the root of the BST. Recursively apply the same logic to the left portion of the list (before the middle) and the right portion (after the middle). Finding the middle node takes linear time each recursion level, and the recursion depth is O(log n), producing a total time complexity of O(n log n). Only recursion stack space is used, so extra space is O(log n). This method demonstrates deeper understanding of linked list traversal and divide and conquer.
Recommended for interviews: Interviewers typically expect the fast–slow pointer solution because it shows you understand how to manipulate a linked list without converting it to another structure. Starting with the array approach is still valuable—it proves you recognize the relationship between a sorted sequence and a balanced binary search tree. Then improving it to the in-place divide-and-conquer version demonstrates stronger problem-solving skills.
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.
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.
JavaScript
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.
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.
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.
C++
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.
| Approach | Complexity |
|---|---|
| Approach 1: Convert Linked List to 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. |
| Approach 2: Fast and Slow Pointer | 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. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Convert Linked List to Array | O(n) | O(n) | When simplicity matters and extra memory is acceptable |
| Fast and Slow Pointer (Divide and Conquer) | O(n log n) | O(log n) | When you want an in-place linked list solution with minimal extra memory |
Convert Sorted Array to Binary Search Tree - Leetcode 108 - Python • NeetCode • 94,636 views views
Watch 9 more video solutions →Practice Convert Sorted List to Binary Search Tree with our built-in code editor and test cases.
Practice on FleetCode