Suppose you wanted to take a sorted array A and build a balanced Binary

Search Tree out of it$.$ How would you do that?

$(1)$ First try building a balanced BST from the following sorted array A by

hand:

A $=\{9,10,15,30,35,42,46,50,57,61,67,72,78,80,89\}$

Hint: The root of your balanced tree will be $50.$

Suppose we define a TNode as follows:

typedef struct TNode$\{$

int data;

TNode$*$ pLeft; $//$left child of this node

TNode$*$ pRight; $//$right child of this node

$\}$ TNode;

$(2)$ Now write a recursive algorithm to solve this problem in the general case:

$/*$ Precondition: A is a sorted array

$*$

$*$ This function creates and returns a balanced BST

$*$ containing the numbers in A$[$start$]$ to A$[$end$]$

$*/$

TNode$*$ createTreeRec$($ int $*$A$,$ int start, int end $)\{$

Hint: There is an O$($n$)$ time algorithm to build a balanced tree from a sorted

array