LeetCode - Convert Sorted Array to Binary Search Tree | Darren's Blog

Given an array where elements are sorted in ascending order, convert it to a height balanced BST
We can pick as the root the number at the center of the array, and recursively generate its left subtree by using the left half of the array, and generate its right subtree by using the right half of the array. After that, we just need to link the subtrees to the root.

public TreeNode sortedArrayToBST(int[] num) {

        if (num == null || num.length == 0)

            return null;

        return recursiveSortedArrayToBST(num, 0, num.length);

    }

    private TreeNode recursiveSortedArrayToBST(int[] num, int leftIndex, int rightIndex) {

        if (leftIndex > rightIndex)     // Empty tree

            return null;

        if (leftIndex == rightIndex)    // Single-node tree

            return new TreeNode(num[leftIndex]);

 

        // Pick the number at the center as the root

        int centerIndex = (leftIndex+rightIndex) / 2;

        TreeNode root = new TreeNode(num[centerIndex]);

 

        // Recursively convert the left half as the left subtree,

        // and convert the right half as the right subtree

        TreeNode left = recursiveSortedArrayToBST(num, leftIndex, centerIndex-1);

        TreeNode right = recursiveSortedArrayToBST(num, centerIndex+1, rightIndex);

 

        // Link the left subtree and the right subtree to the root

        root.left = left;

        root.right = right;

 

        return root;

    }

Read full article from LeetCode - Convert Sorted Array to Binary Search Tree | Darren's Blog