Question

The goal of this assignment is to reinforce the tree data structure in C++. Specifically, the assignment is to do the following: Binary search trees have their best performance when they are balanced, which means that at each node, n, the height of the left subtree of n is within one of the height of the right subtree of n. Write a function (and a test program) which takes a sorted list of entries and produces a balanced binary search tree.

Answer 1

Function:

Node *ArrayToBst(int arr[],int l,int r)
{
if(l>r)
return NULL;

int mid=(l+r)/2;
Node *root = newNode(arr[mid]);
root->left = ArrayToBs(arr,l,mid-1);
root->right = ArrayToBs(arr,mid+1,r);

return root;
}