Posts Array to BST (geeksforgeeks - SDE Sheet)
Post
Cancel

Array to BST (geeksforgeeks - SDE Sheet)

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.

geeksforgeeks

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;
    }

}
This post is licensed under CC BY 4.0 by the author.