109. Convert Sorted List to Binary Search Tree
Problem Description
The problem presents a singly linked list sorted in ascending order and asks us to convert it into a height-balanced binary search tree (BST). A height-balanced binary tree is one where the depth of the two subtrees of every node never differs by more than one. A binary search tree is a binary tree in which each node has a unique value, and the left subtree of a node only contains nodes with values lesser than the node's value, and the right subtree only contains nodes with values greater than the node's value.
Intuition
The solution is rooted in the properties of a binary search tree and a height-balanced tree. In a BST, the left child is always less than the parent, and the right child is always greater. For the tree to be height-balanced, we ideally want to choose the middle element of the sorted list as the root, so that the number of elements on both sides of the root is balanced or off by one at most.
Here is how we arrive at the solution approach:
-
Convert Linked List to Array: Since we want to access the middle element and the linked list does not support random access, we first convert the linked list to an array.
-
Recursive BST Construction: Given the sorted array, we can construct the BST recursively.
- We choose the middle element of the array as the root node. This ensures that our tree is height-balanced.
- We recursively apply the same logic to construct the left subtree from the elements to the left of the chosen middle element.
- Similarly, we construct the right subtree from the elements to the right of the chosen middle element.
- The base case of the recursion is when we have no elements (start index is greater than the end index), at which point we return
None
, indicating no node is to be created.
This approach effectively builds a height-balanced BST, as the middle element becomes the root for every sub-array (or sub-tree), ensuring balanced height at every level.
Learn more about Tree, Binary Search Tree, Linked List, Divide and Conquer and Binary Tree patterns.
Solution Approach
The provided Python solution follows a two-step process to convert a sorted linked list to a height-balanced BST.
-
Convert Linked List to Array: The sorted linked list is first converted to an array to facilitate easy access to the middle element, which is crucial for constructing a balanced BST. This is done simply by iterating over the linked list in a while loop and appending each node's value to an array called
nums
.nums = [] while head: nums.append(head.val) head = head.next
-
Recursive BST Construction: With the array in hand, we can now think about constructing the BST. Here, we employ a divide and conquer strategy, making use of recursion to build the BST:
- A helper function
buildBST
takes the part of the array we're interested in (start
toend
) and recursively constructs the tree.
def buildBST(nums, start, end): if start > end: return None mid = (start + end) >> 1 return TreeNode( nums[mid], buildBST(nums, start, mid - 1), buildBST(nums, mid + 1, end) )
-
Inside
buildBST
, we find the middle of the current array segment using the bitwise right shift operation>>
, which is equivalent to integer division by 2. This operation is used to find the indexmid
which is the middle element of thenums
list (or subarray). -
A new
TreeNode
is created using the value at themid
index. For the left subtree, we recursively callbuildBST
on the subarray beforemid
. For the right subtree, we callbuildBST
on the subarray aftermid
. -
The recursion base case is when the
start
index exceeds theend
index, meaning there are no more elements to build a subtree from, so we returnNone
.
- A helper function
After setting up the nums
array and the buildBST
function, the sortedListToBST
function calls buildBST
once with the full array to initiate the recursive tree-building process.
return buildBST(nums, 0, len(nums) - 1)
This line starts constructing the BST with the entire range of the array indices, effectively starting from the root. Through recursive calls, the entire BST is built in memory and finally returned by the function. The result is a height-balanced BST, as each subtree is constructed from the middle of a sorted sequence, keeping the tree's height as minimal as possible while satisfying the BST property.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's go through how the solution approach works using a small example. Suppose we have a sorted singly linked list with the values [1, 2, 3, 4, 5]
. We want to convert this list into a height-balanced BST.
We first convert our linked list into an array so we can easily access the middle element. After this conversion step, we obtain the array nums = [1, 2, 3, 4, 5]
. Now, we are prepared to initiate the construction of our BST.
By applying a recursive BST construction, we will perform the following steps:
-
First call of
buildBST
: We begin with the full range of the array indices, callingbuildBST(nums, 0, 4)
. -
The middle element of
nums
between index0
and index4
isnums[2]
, which is3
. This value becomes the root of our BST.3 / \ ? ?
The question marks (
?
) represent the subtrees that we haven't constructed yet. -
We then construct the left subtree with elements to the left of our middle element (3), indexes
0
to1
, and the right subtree with elements to the right, indexes3
to4
, again using recursive calls tobuildBST
. -
Recursive call for the left subtree:
buildBST(nums, 0, 1)
.- The middle of the subarray
nums[0...1]
isnums[1]
(2
). This is the root of the left subtree.
3 / \ 2 ? / \ ? ?
-
We call
buildBST(nums, 0, 0)
for its left child andbuildBST(nums, -1)
for its right child. The right child call immediately returnsNone
since the start index is greater than the end index. -
For the left child, the middle of
nums[0...0]
isnums[0]
(1
), which becomes the left child of node2
.
3 / \ 2 ? / \ 1 None
- The middle of the subarray
-
Recursive call for the right subtree:
buildBST(nums, 3, 4)
.- The middle of the subarray
nums[3...4]
isnums[3]
(4
), which becomes the root of the right subtree.
3 / \ 2 4 / \ \ 1 None ?
- Similarly, we call
buildBST(nums, 4, 4)
for its right child (left child call returnsNone
again), yielding the middle elementnums[4]
(5
), the right child of node4
.
3 / \ 2 4 / \ \ 1 None 5
- The middle of the subarray
-
We have now completed constructing all the subtrees recursively. The resulting BST looks like this:
3 / \ 2 4 / \ 1 5
This example tree showcases the result of the process: a balanced BST where each parent node is the median of the values in its subtree, with no subtree depths differing by more than one. The algorithm correctly positioned each element of the sorted array into a tree that respects both BST and height-balanced conditions.
Solution Implementation
1# Definition for singly-linked list.
2class ListNode:
3 def __init__(self, val=0, next=None):
4 self.val = val
5 self.next = next
6
7# Definition for a binary tree node.
8class TreeNode:
9 def __init__(self, val=0, left=None, right=None):
10 self.val = val
11 self.left = left
12 self.right = right
13
14class Solution:
15 def sortedListToBST(self, head: ListNode) -> TreeNode:
16 # Helper function to build a BST from the sorted list values.
17 def build_bst(nums, start, end):
18 if start > end:
19 return None # Base case: no more nodes to add
20
21 mid = (start + end) // 2 # Find the middle element index
22 # Create a TreeNode from the middle element
23 node = TreeNode(
24 nums[mid],
25 build_bst(nums, start, mid - 1), # Left subtree
26 build_bst(nums, mid + 1, end) # Right subtree
27 )
28 return node # Return the current node
29
30 # Convert the linked list to a list to facilitate tree construction
31 nums = []
32 while head:
33 nums.append(head.val)
34 head = head.next
35
36 # Build the BST using the list of values
37 return build_bst(nums, 0, len(nums) - 1)
38
1/**
2 * Definition for singly-linked list.
3 */
4class ListNode {
5 int val;
6 ListNode next;
7 ListNode() {}
8 ListNode(int val) { this.val = val; }
9 ListNode(int val, ListNode next) { this.val = val; this.next = next; }
10}
11
12/**
13 * Definition for a binary tree node.
14 */
15class TreeNode {
16 int val;
17 TreeNode left;
18 TreeNode right;
19 TreeNode() {}
20 TreeNode(int val) { this.val = val; }
21 TreeNode(int val, TreeNode left, TreeNode right) {
22 this.val = val;
23 this.left = left;
24 this.right = right;
25 }
26}
27
28class Solution {
29 /**
30 * Converts a sorted singly-linked list to a height-balanced binary search tree.
31 *
32 * @param head The head node of the sorted linked list.
33 * @return The root node of the constructed binary search tree.
34 */
35 public TreeNode sortedListToBST(ListNode head) {
36 // Convert the linked list to an ArrayList to utilize random access.
37 List<Integer> numbers = new ArrayList<>();
38 // Traverse the linked list and populate the ArrayList with its elements.
39 for (ListNode current = head; current != null; current = current.next) {
40 numbers.add(current.val);
41 }
42 // Initialize the binary search tree construction process.
43 return buildBST(numbers, 0, numbers.size() - 1);
44 }
45
46 /**
47 * Recursively constructs a height-balanced binary search tree from a list of numbers.
48 *
49 * @param numbers A list of sorted numbers from which to construct the BST.
50 * @param start The starting index for the current subtree in the list.
51 * @param end The ending index for the current subtree in the list.
52 * @return The root node of the constructed subtree.
53 */
54 private TreeNode buildBST(List<Integer> numbers, int start, int end) {
55 // Base case: if the start index exceeds the end index, no numbers are left to form a subtree.
56 if (start > end) {
57 return null;
58 }
59 // Find the middle index. This will be the root of the subtree.
60 int mid = start + (end - start) / 2;
61 // Create a new TreeNode with the middle number.
62 TreeNode root = new TreeNode(numbers.get(mid));
63 // Recursively build the left subtree from the first half of the number range.
64 root.left = buildBST(numbers, start, mid - 1);
65 // Recursively build the right subtree from the second half of the number range.
66 root.right = buildBST(numbers, mid + 1, end);
67 return root;
68 }
69}
70
1// A struct defining a node in a singly-linked list.
2struct ListNode {
3 int val;
4 ListNode *next;
5 ListNode() : val(0), next(nullptr) {}
6 ListNode(int x) : val(x), next(nullptr) {}
7 ListNode(int x, ListNode *next) : val(x), next(next) {}
8};
9
10// A struct defining a node in a binary tree.
11struct TreeNode {
12 int val;
13 TreeNode *left;
14 TreeNode *right;
15 TreeNode() : val(0), left(nullptr), right(nullptr) {}
16 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
17 TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
18};
19
20class Solution {
21public:
22 // Converts a sorted singly-linked list to a height-balanced binary search tree.
23 TreeNode* sortedListToBST(ListNode* head) {
24 // Initialize a vector to store the elements of the list.
25 vector<int> nums;
26
27 // Populate the vector with values from the linked list.
28 while (head != nullptr) {
29 nums.push_back(head->val);
30 head = head->next;
31 }
32
33 // Recursively build the BST from the sorted array.
34 return buildBST(nums, 0, nums.size() - 1);
35 }
36
37private:
38 // Recursively constructs a height-balanced BST from a sorted array segment.
39 TreeNode* buildBST(vector<int>& nums, int start, int end) {
40 // Base case: when the start index exceeds the end index.
41 if (start > end) {
42 return nullptr;
43 }
44
45 // Calculate mid index to create a balanced BST.
46 int mid = start + (end - start) / 2;
47
48 // Create a new tree node with the middle element as root.
49 TreeNode* root = new TreeNode(nums[mid]);
50
51 // Recursively build left subtree from the left segment of the array.
52 root->left = buildBST(nums, start, mid - 1);
53
54 // Recursively build right subtree from the right segment of the array.
55 root->right = buildBST(nums, mid + 1, end);
56
57 return root; // Return the newly built tree node.
58 }
59};
60
1// Definition for singly-linked list node.
2interface ListNode {
3 val: number;
4 next: ListNode | null;
5}
6
7// Definition for a binary tree node.
8interface TreeNode {
9 val: number;
10 left: TreeNode | null;
11 right: TreeNode | null;
12}
13
14/**
15 * Finds the middle element in the linked list using the slow and fast pointer technique.
16 * @param {ListNode | null} start - The starting node of the linked list or sub-list.
17 * @param {ListNode | null} end - The end limit for the list or sub-list (exclusive).
18 * @return {ListNode | null} - The middle node of the list or sub-list.
19 */
20const findMiddleNode = (start: ListNode | null, end: ListNode | null): ListNode | null => {
21 let fast = start;
22 let slow = start;
23 // Traverse the list with two pointers, fast moves at double the speed of slow.
24 while (fast !== end && fast.next !== end) {
25 fast = fast.next.next;
26 slow = slow.next;
27 }
28 // When fast reaches the end, slow is at the middle.
29 return slow;
30};
31
32/**
33 * Recursively builds a height-balanced binary search tree from the sorted list.
34 * @param {ListNode | null} start - The starting node of the current list or sub-list.
35 * @param {ListNode | null} end - The end limit for the current list or sub-list (exclusive).
36 * @return {TreeNode | null} - The root node of the constructed binary search tree.
37 */
38const buildBSTFromSortedList = (start: ListNode | null, end: ListNode | null): TreeNode | null => {
39 // Base case: if start equals end, we've reached the bounds of the current sub-list.
40 if (start === end) {
41 return null;
42 }
43 // Get the middle node to act as the root of the subtree.
44 const midNode = findMiddleNode(start, end);
45 // Construct the TreeNode using the value from midNode and recursive calls to build left and right subtrees.
46 return {
47 val: midNode.val,
48 left: buildBSTFromSortedList(start, midNode), // Left subtree comes from list elements before mid
49 right: buildBSTFromSortedList(midNode.next, end) // Right subtree comes from elements after mid
50 };
51};
52
53/**
54 * Converts a sorted linked list to a height-balanced binary search tree.
55 * @param {ListNode | null} head - The head of the sorted linked list.
56 * @return {TreeNode | null} - The root of the constructed binary search tree.
57 */
58function sortedListToBST(head: ListNode | null): TreeNode | null {
59 // Build the BST from the linked list starting from head to null (end of the list).
60 return buildBSTFromSortedList(head, null);
61}
62
Time and Space Complexity
Time Complexity
The given code snippet performs two main operations: one to convert the singly linked list to an array (nums
), and one to build the binary search tree (BST) from the array.
-
Converting the singly linked list to an array: The while loop iterates through each of the nodes in the linked list exactly once to populate the
nums
list with the node values. Letn
be the number of nodes in the linked list. This process takesO(n)
time. -
Building the BST from the array: The
buildBST
function is a recursive function called on each level of the final BST. Since a balanced BST has a height oflog(n)
, and each level of recursive calls processesn
nodes in total (though each individual call processes fewer nodes, and these calls are mutually exclusive), you can think of this aslog(n)
recursive levels, each doingO(n)
work in total. Therefore, this also takesO(n log n)
time.
Overall, since both operations are performed sequentially, the total time complexity of the algorithm is O(n) + O(n log n)
, which simplifies to O(n log n)
.
Space Complexity
-
Space used by the array (
nums
): The array that holds all the node values from the linked list consumesO(n)
space. -
Space used by the recursion stack: The recursive
buildBST
function will consume space on the execution stack. In the worst case (when the BST is completely unbalanced), the height of the recursion tree can ben
(though in this scenario, quick balance check confirms it wouldn't be the case because we're constructing a balanced tree), leading to a space complexity ofO(n)
. However, since we are constructing a balanced BST, the height of the recursion stack will beO(log n)
in the best and average cases. -
Space for the BST nodes: The space required for the nodes of the built BST is not usually counted in the space complexity, as it's required for the output of the algorithm and is not auxiliary space. However, technically it also takes
O(n)
space.
The dominating factors here are the array (O(n)
) and the space for the recursion stack (O(log n)
for a balanced BST), which adds up to O(n)
overall since O(n)
is larger than O(log n)
.
Hence, the overall space complexity is O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm is best for finding the shortest distance between two points in an unweighted graph?
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
Binary Search Tree Intro Definition A Binary Search Tree or BST is a rooted binary tree with the value of each internal node being greater than all the values in the respective node's left subtree and less than the ones in its right subtree An empty tree is a BST since it satisfies the
Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained
Want a Structured Path to Master System Design Too? Don’t Miss This!