PROBLEM DESCRIPTION
Given a sorted array. Convert it into a Height Balanced Binary Search Tree (BST). Return the root of the BST.
Height-balanced BST means a binary tree in which the depth of the left subtree and the right subtree of every node never differ by more than 1.
SOLUTION
We can solve this by using a recursive approach to convert a sorted array into a balanced Binary Search Tree (BST). The key idea is to select the middle element of the array (or subarray) as the root of the BST, ensuring that the tree remains balanced.
The middle element splits the array into two halves: the left half is used to recursively build the left subtree, and the right half is used for the right subtree. The base case of the recursion occurs when the left index exceeds the right index, meaning there are no elements to process, so we return null.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public Node sortedArrayToBST(int[] nums) {
return createTree(nums, 0, nums.length - 1);
}
public Node createTree(int[] nums, int l, int r) {
// Base case: if left index exceeds right index, return null (no node)
if (l > r)
return null;
// Find the middle element to be the root node of the current subtree
int mid = (l + r) / 2;
// Create a new node with the middle element
Node node = new Node(nums[mid]);
// Recursively build the left subtree using the left half of the array
node.left = createTree(nums, l, mid - 1);
// Recursively build the right subtree using the right half of the array
node.right = createTree(nums, mid + 1, r);
// Return the created node (root of the current subtree)
return node;
}
}