109. Convert Sorted List to Binary Search Tree

MediumTreeBinary Search TreeLinked ListDivide and ConquerBinary 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 to end) 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 index mid which is the middle element of the nums list (or subarray).
- A new TreeNode is created using the value at the mid index. For the left subtree, we recursively call buildBST on the subarray before mid. For the right subtree, we call buildBST on the subarray after mid.
- The recursion base case is when the start index exceeds the end index, meaning there are no more elements to build a subtree from, so we return None.

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 Evaluator

Example 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, calling buildBST(nums, 0, 4).
The middle element of nums between index 0 and index 4 is nums[2], which is 3. 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 to 1, and the right subtree with elements to the right, indexes 3 to 4, again using recursive calls to buildBST.
Recursive call for the left subtree: buildBST(nums, 0, 1).
- The middle of the subarray nums[0...1] is nums[1] (2). This is the root of the left subtree.
```
       3
      / \
     2   ?
    / \
  ?   ?
```
- We call buildBST(nums, 0, 0) for its left child and buildBST(nums, -1) for its right child. The right child call immediately returns None since the start index is greater than the end index.
- For the left child, the middle of nums[0...0] is nums[0] (1), which becomes the left child of node 2.
```
       3
      / \
     2   ?
    / \
   1  None
```

Recursive call for the right subtree: buildBST(nums, 3, 4).

The middle of the subarray nums[3...4] is nums[3] (4), which becomes the root of the right subtree.

Similarly, we call buildBST(nums, 4, 4) for its right child (left child call returns None again), yielding the middle element nums[4] (5), the right child of node 4.

We have now completed constructing all the subtrees recursively. The resulting BST looks like this:

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. Let n be the number of nodes in the linked list. This process takes O(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 of log(n), and each level of recursive calls processes n nodes in total (though each individual call processes fewer nodes, and these calls are mutually exclusive), you can think of this as log(n) recursive levels, each doing O(n) work in total. Therefore, this also takes O(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 consumes O(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 be n (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 of O(n). However, since we are constructing a balanced BST, the height of the recursion stack will be O(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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don't know