Given an array A[] where elements are 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 depth of the two subtrees of every node never differs by more than 1.

Example 1

Input: A[] = [1, 2, 3]
Output: A Balanced BST
     2
   /  \
  1    3 

Example 2

Input: A[] = [1, 2, 3, 4]
Output: A Balanced BST
      3
    /  \
   2    4
 /
1