Question

Code using JAVA:

must include "Main Method" for IDE testing!

/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
  
}
};

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

Answer 1

Java code

class TreeNode {
    
    int val;
    TreeNode left, right;
    
    TreeNode(int d) {
        val = d;
        left = null;
        right = null;
    }
}

public class Solution {
  
    public static TreeNode sortedArrayToBST(int sortedArray[], int left, int right) {

        if (left > right) return null;
       
        int mid = (left + right) / 2;
        TreeNode node = new TreeNode(sortedArray[mid]);

        node.left = sortedArrayToBST(sortedArray, left, mid - 1);

        node.right = sortedArrayToBST(sortedArray, mid + 1, right);
        
        return node;
    }

    public static void inOrder(TreeNode node) {
        if (node == null) return;
        inOrder(node.left);
        System.out.print(node.val + " ");
        inOrder(node.right);
    }
    
    public static void main(String[] args) {
        int sortedArray[] = new int[]{-10,-3,0,5,9};
        int n = sortedArray.length;
        TreeNode root = sortedArrayToBST(sortedArray, 0, n - 1);
        System.out.println("Inorder traversal");
        inOrder(root);
    }
}