108. Convert Sorted Array to Binary Search Tree
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:
- Find the middle element of the current segment of the array.
- Make this element the root of the current subtree.
- Recursively perform the same action on the left half of the array to create the left subtree.
- 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.
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:
-
A recursive helper function called
dfs
is defined, which takes two parameters,l
andr
, which represent the left and right bounds of the segment of thenums
array that we are currently considering. This function is responsible for creating nodes in the BST. -
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. -
The middle index of the current segment is found using the expression
(l + r) >> 1
, which is equivalent to finding the average ofl
andr
and then taking the floor of the result. The bitwise right shift operator>>
is used here to efficiently divide the sum by 2. -
The middle element of
nums
, located at indexmid
, is the value of the root node for the current segment of the array. ATreeNode
is created with this value. -
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 boundsl
tomid - 1
, while the recursivedfs
call for the right subtree uses the boundsmid + 1
tor
. -
After the left and right subtrees are created via recursion, a new
TreeNode
withnums[mid]
as its value and the created left and right subtrees as its children is returned. -
The outer function
sortedArrayToBST
initializes the construction process by callingdfs(0, len(nums) - 1)
with the full range of the input arraynums
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.
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 use a small example to illustrate the solution approach. We are given the following sorted array:
nums = [-10, -3, 0, 5, 9]
Using the steps outlined in the solution approach, we would construct a height-balanced BST as follows:
-
We first call the
dfs
function with the initial bounds set tol = 0
andr = 4
(assuming zero-based array indexing). -
We find the middle element of
nums
between indices 0 and 4. The midpoint calculation would be(0 + 4) >> 1
, which simplifies to2
. Hence, the middle element isnums[2]
, which is0
. -
We create a
TreeNode
with a value of0
. This is the root of our BST. -
Now we need to build the left subtree. We make a recursive
dfs
call with the new bounds,l = 0
andr = 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 to0
. The element at that index innums
is-10
, so we create aTreeNode
with value-10
. - For the left child of
-10
, thedfs
call withl = 0
andr = -1
returnsNone
sincel > r
. - For the right child, we have
nums[mid + 1]
wheremid
is0
. We make a recursive call withl = 1
andr = 1
.mid
for this subarray is1
and the element at that index is-3
, so-3
becomes the right child node of-10
.
- For this subarray, we take the middle element as the root for the left subtree. The midpoint is
-
Returning to our root
0
, we build the right subtree with a newdfs
call using the boundsl = 3
(mid + 1
) andr = 4
, focusing on the subarray[5, 9]
.- The midpoint here is
(3 + 4) >> 1
, which is3
. The element at index3
innums
is5
. So,5
becomes the left child node of the right subtree of0
. - The left child of
5
would beNone
since a recursive call with boundsl = 3
andr = 2
returnsNone
. - For the right child, the new midpoint is
4
(mid + 1
wheremid = 3
), leading to the element9
being selected. Hence,9
is the right child node of5
.
- The midpoint here is
-
At this point, we have successfully constructed all parts of the BST, which would look like this:
0 / \ -3 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
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.
Is the following code DFS or BFS?
void search(Node root) { if (!root) return; visit(root); root.visited = true; for (Node node in root.adjacent) { if (!node.visited) { search(node); } } }
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
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
Want a Structured Path to Master System Design Too? Donāt Miss This!