108. Convert Sorted Array to Binary Search Tree

EasyTreeBinary Search TreeArrayDivide and ConquerBinary Tree
Leetcode Link

Problem Description

The problem gives us an integer array called nums which is sorted in ascending order. Our task is to convert this sorted array into a height-balanced binary search tree (BST). A height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Intuition

The solution to the problem lies in the properties of a binary search tree and the characteristics of a sorted array. A binary search tree is a node-based binary tree where each node has the following properties:

  • The left subtree of a node contains only nodes with keys less than the node's key.
  • The right subtree of a node contains only nodes with keys greater than the node's key.
  • The left and right subtrees must also be binary search trees.

The challenge is to ensure that the BST is height-balanced. To achieve this, we need to pick the middle element from the sorted array and make it a root, so that the elements to the left, which are lesser, form the left subtree, and the elements to the right, which are greater, form the right subtree.

To construct the BST, we apply a recursive strategy:

  1. Find the middle element of the current segment of the array.
  2. Make this element the root of the current subtree.
  3. Recursively perform the same action on the left half of the array to create the left subtree.
  4. Recursively perform the same action on the right half of the array to create the right subtree.

This divide and conquer approach will ensure that the tree remains height-balanced, as each subtree is constructed from segments of the array that are roughly half the size of the original segment.

By carefully selecting the middle element of the array as the root for each recursive step, the resulting tree satisfies the conditions of a binary search tree as well as being height-balanced.

Learn more about Tree, Binary Search Tree, Divide and Conquer and Binary Tree patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Which type of traversal does breadth first search do?

Solution Approach

To implement the solution using the given Python code, the following steps are taken, which relate to the concepts of depth-first search (DFS) and recursion:

  1. A recursive helper function called dfs is defined, which takes two parameters, l and r, which represent the left and right bounds of the segment of the nums array that we are currently considering. This function is responsible for creating nodes in the BST.

  2. The base case for the recursive function is checked: if l > r, it means we have considered all elements in this segment, and there is nothing to create a node with. Therefore, None is returned, indicating the absence of a subtree.

  3. The middle index of the current segment is found using the expression (l + r) >> 1, which is equivalent to finding the average of l and r and then taking the floor of the result. The bitwise right shift operator >> is used here to efficiently divide the sum by 2.

  4. The middle element of nums, located at index mid, is the value of the root node for the current segment of the array. A TreeNode is created with this value.

  5. To build a binary search tree, we need to recursively build the left and right subtrees. The recursive dfs call for the left subtree uses the bounds l to mid - 1, while the recursive dfs call for the right subtree uses the bounds mid + 1 to r.

  6. After the left and right subtrees are created via recursion, a new TreeNode with nums[mid] as its value and the created left and right subtrees as its children is returned.

  7. The outer function sortedArrayToBST initializes the construction process by calling dfs(0, len(nums) - 1) with the full range of the input array nums as the bounds for the entire tree.

This approach efficiently builds the binary search tree by always dividing the array into two halves, ensuring the tree is balanced. The tree's properties as a binary search tree are maintained because we construct the left and right subtrees from elements that are strictly less than or greater than the root of any subtree, thus satisfying all the properties of the BST.

The choice of using a recursive function encapsulates the logic for both creating TreeNode instances and ensuring that we honor the bounds of the current array segment at each step, simplifying the complexity of the task at each recursive call.

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

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Example Walkthrough

Let's use a small example to illustrate the solution approach. We are given the following sorted array:

1nums = [-10, -3, 0, 5, 9]

Using the steps outlined in the solution approach, we would construct a height-balanced BST as follows:

  1. We first call the dfs function with the initial bounds set to l = 0 and r = 4 (assuming zero-based array indexing).

  2. We find the middle element of nums between indices 0 and 4. The midpoint calculation would be (0 + 4) >> 1, which simplifies to 2. Hence, the middle element is nums[2], which is 0.

  3. We create a TreeNode with a value of 0. This is the root of our BST.

  4. Now we need to build the left subtree. We make a recursive dfs call with the new bounds, l = 0 and r = 1 (mid - 1), focusing on the subarray [-10, -3].

    • For this subarray, we take the middle element as the root for the left subtree. The midpoint is (0 + 1) >> 1, simplifying to 0. The element at that index in nums is -10, so we create a TreeNode with value -10.
    • For the left child of -10, the dfs call with l = 0 and r = -1 returns None since l > r.
    • For the right child, we have nums[mid + 1] where mid is 0. We make a recursive call with l = 1 and r = 1. mid for this subarray is 1 and the element at that index is -3, so -3 becomes the right child node of -10.

  5. Returning to our root 0, we build the right subtree with a new dfs call using the bounds l = 3 (mid + 1) and r = 4, focusing on the subarray [5, 9].

    • The midpoint here is (3 + 4) >> 1, which is 3. The element at index 3 in nums is 5. So, 5 becomes the left child node of the right subtree of 0.
    • The left child of 5 would be None since a recursive call with bounds l = 3 and r = 2 returns None.
    • For the right child, the new midpoint is 4 (mid + 1 where mid = 3), leading to the element 9 being selected. Hence, 9 is the right child node of 5.

  6. At this point, we have successfully constructed all parts of the BST, which would look like this:

1       0
2      / \
3    -3   5
4    /     \
5  -10     9

By following these steps, we have successfully transformed the sorted array nums into a height-balanced BST. The recursive process ensures that each subtree is constructed from the middle of the subarray it refers to, making the tree balanced and maintaining the binary search tree property.

Solution Implementation

1class TreeNode:
2    # Definition for a binary tree node.
3    def __init__(self, value=0, left=None, right=None):
4        self.value = value
5        self.left = left
6        self.right = right
7
8class Solution:
9    def sortedArrayToBST(self, nums):
10        """
11        Converts a sorted array into a height-balanced binary search tree (BST).
12        A height-balanced binary tree is a binary tree in which the depth of the two
13        subtrees of every node never differ by more than one.
14
15        Args:
16        nums : List[int]
17            An integer array which is sorted in non-decreasing order.
18
19        Returns:
20        TreeNode
21            The root of the otherwise height-balanced binary search tree.
22        """
23      
24        def convert_to_bst(left_index, right_index):
25            """
26            Recursively construct BST from nums array using the divide and conquer approach.
27          
28            Args:
29            left_index : int
30                The starting index of the subarray to be processed.
31            right_index : int
32                The ending index of the subarray to be processed.
33
34            Returns:
35            TreeNode
36                The constructed BST node (root for the subarray).
37            """
38            # Base case: If the left index is greater than the right index,
39            # the subarray is empty, and there is no tree to construct.
40            if left_index > right_index:
41                return None
42
43            # Choosing the middle element of the subarray to be the root of the BST.
44            middle_index = (left_index + right_index) // 2
45
46            # Recursively constructing the left subtree.
47            left_subtree = convert_to_bst(left_index, middle_index - 1)
48
49            # Recursively constructing the right subtree.
50            right_subtree = convert_to_bst(middle_index + 1, right_index)
51
52            # Creating the root node with the middle element, passing the
53            # left and right subtrees as its children.
54            return TreeNode(nums[middle_index], left_subtree, right_subtree)
55
56        # Initiating the recursive function with the whole array range.
57        return convert_to_bst(0, len(nums) - 1)
58
1/**
2 * Definition for a binary tree node.
3 */
4class TreeNode {
5    int val; // Node value
6    TreeNode left; // Left child
7    TreeNode right; // Right child
8
9    // Constructor
10    TreeNode() {}
11
12    // Constructor with value
13    TreeNode(int val) { this.val = val; }
14
15    // Constructor with value, left child, and right child
16    TreeNode(int val, TreeNode left, TreeNode right) {
17        this.val = val;
18        this.left = left;
19        this.right = right;
20    }
21}
22
23class Solution {
24    private int[] nums;
25
26    /**
27     * Convert a sorted array into a height-balanced binary search tree.
28     *
29     * @param nums Sorted array of integers
30     * @return Root of the height-balanced binary search tree
31     */
32    public TreeNode sortedArrayToBST(int[] nums) {
33        this.nums = nums;
34        return constructBSTRecursive(0, nums.length - 1);
35    }
36
37    /**
38     * Recursive helper method to construct BST from the sorted array.
39     *
40     * @param left  The starting index of the subarray
41     * @param right The ending index of the subarray
42     * @return The root of the BST subtree constructed from subarray
43     */
44    private TreeNode constructBSTRecursive(int left, int right) {
45        // Base case: If left > right, the subarray is empty and should return null
46        if (left > right) {
47            return null;
48        }
49      
50        // Find the middle element to maintain BST properties. Use `left + (right - left) / 2`
51        // to avoid integer overflow
52        int mid = left + (right - left) / 2;
53
54        // Recursively construct the left subtree
55        TreeNode leftSubtree = constructBSTRecursive(left, mid - 1);
56      
57        // Recursively construct the right subtree
58        TreeNode rightSubtree = constructBSTRecursive(mid + 1, right);
59      
60        // Create a new TreeNode with the mid element and the previously constructed left and right subtrees
61        TreeNode node = new TreeNode(nums[mid], leftSubtree, rightSubtree);
62      
63        return node;
64    }
65}
66
1/**
2 * Definition for a binary tree node.
3 */
4struct TreeNode {
5    int val;
6    TreeNode *left;
7    TreeNode *right;
8
9    // Constructor for a tree node with a given value and optional left and right children.
10    TreeNode(int x, TreeNode *left = nullptr, TreeNode *right = nullptr) 
11        : val(x), left(left), right(right) {}
12};
13
14class Solution {
15public:
16    /**
17     * Converts a sorted array into a binary search tree with minimal height.
18     * @param nums The vector of integers sorted in non-decreasing order.
19     * @return A pointer to the root of the constructed binary search tree.
20     */
21    TreeNode* sortedArrayToBST(vector<int>& nums) {
22        // Recursive function that converts a subarray into a BST.
23        function<TreeNode*(int, int)> convertToBST = [&](int leftIndex, int rightIndex) -> TreeNode* {
24            // Base case: if left index is greater than right, the subarray is empty and returns nullptr.
25            if (leftIndex > rightIndex) {
26                return nullptr;
27            }
28
29            // Choose the middle element as the root to maintain minimal height.
30            int mid = leftIndex + (rightIndex - leftIndex) / 2;
31
32            // Recursively construct the left subtree.
33            auto leftChild = convertToBST(leftIndex, mid - 1);
34          
35            // Recursively construct the right subtree.
36            auto rightChild = convertToBST(mid + 1, rightIndex);
37
38            // Create and return the current tree node with its left and right children.
39            return new TreeNode(nums[mid], leftChild, rightChild);
40        };
41
42        // Start the recursive process with the full array range.
43        return convertToBST(0, nums.size() - 1);
44    }
45};
46
1interface TreeNode {
2    val: number;
3    left: TreeNode | null;
4    right: TreeNode | null;
5}
6
7/**
8 * Converts a sorted array into a height-balanced binary search tree.
9 * @param {number[]} nums - A sorted array of numbers.
10 * @return {TreeNode | null} - The root node of the constructed BST, or null if the array is empty.
11 */
12function sortedArrayToBST(nums: number[]): TreeNode | null {
13    // Determine the length of the array.
14    const length = nums.length;
15  
16    // Base Case: If array is empty, return null.
17    if (length === 0) {
18        return null;
19    }
20  
21    // Find the middle index of the array.
22    const middleIndex = Math.floor(length / 2);
23  
24    // Recursively construct the BST by choosing the middle element of the 
25    // current subsection as the root, and the left and right subsections as the left and right subtrees.
26    const rootNode = {
27        val: nums[middleIndex],
28        left: sortedArrayToBST(nums.slice(0, middleIndex)),
29        right: sortedArrayToBST(nums.slice(middleIndex + 1))
30    };
31  
32    // Return the root node of the BST.
33    return rootNode;
34}
35
36// Note: No class has been defined as per the instructions.
37// TreeNode and sortedArrayToBST are both defined in the global scope.
38
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which technique can we use to find the middle of a linked list?

Time and Space Complexity

The time complexity of the given code is O(n), where n is the number of elements in the input list nums. This is because each element of the array is visited exactly once to construct each node of the resulting binary search tree (BST).

The space complexity of the code is also O(n) if we consider the space required for the output BST. However, if we only consider the auxiliary space (excluding the space taken by the output), it is O(log n) in the best case (which is the height of a balanced BST). The worst-case space complexity would be O(n) if the binary tree is degenerated (i.e., every node only has one child) which would be the case if the input list is sorted in strictly increasing or decreasing order.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

Recommended Readings

Everything About Trees

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

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

Divide and Conquer Intro

https algomonster s3 us east 2 amazonaws com cover_photos dnd svg Divide and Conquer The main idea of divide and conquer is to split the main problem into two smaller components assuming that each one of the components had already been solved recursively and then try to solve the bigger

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ