Posts Convert Sorted Array to Binary Search Tree
Post
Cancel

Convert Sorted Array to Binary Search Tree

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;
 *     }
 * }
 */
This post is licensed under CC BY 4.0 by the author.