Given an array, arr[] having all the elements sorted in ascending order, write a program to convert it to a height balanced BST.

Problem Note

• The height-balanced binary tree is defined as a binary tree in which the maximum depth of the two subtrees of every node is 1.

Example 1

Input: arr[] = [1, 2, 3]
Output: A Balanced BST
     2
   /  \
  1    3 
Explanation: The maximum difference between the two subtrees is 1. Here, the difference between the depth of the two subtrees is 0.

Example 2

Input: arr[] = [1, 2, 3, 4]
Output: A Balanced BST
      3
    /  \
   2    4
 /
1
Explanation: The resultant BST is height balanced as the maximum difference between the left and right subtree is 1.