PROBLEM DESCRIPTION
Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.
leetcode
SOLUTION
We can solve this recursively:
- First get the middle element from range [start, end]. Let’s say it’s idx.
- Create a node using the value present at idx index.
- Now recursively solve the sub-problem for left and right sub-trees for this node.
- The left sub-tree will be recur call to func(start, idx-1)
- The right sub-tree will be recur call to func(idx+1, end)
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return builder(nums, 0, nums.length-1);
}
public TreeNode builder(int[] nums, int i, int j) {
// Base case: When the left index is greater than the right index, return null.
if (i > j) {
return null;
}
// Calculate the index of the middle element.
int idx = (i + j) / 2;
// Create a new tree node with the middle element as the root value.
TreeNode node = new TreeNode(nums[idx]);
// Recursively build the left subtree using elements from the left half of the array.
node.left = builder(nums, i, idx - 1);
// Recursively build the right subtree using elements from the right half of the array.
node.right = builder(nums, idx + 1, j);
return node;
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/