C++ Programming Exercise: Implement a function Node * buildTree(int nums[], int

Question

C++ Programming Exercise:

Implement a function Node * buildTree(int nums[], int length); that returns a pointer to the root of a balanced binary search tree containing the same values as nums. Assume that the values in nums are all distinct.

Hint: Sort the array first and then recursively create trees with the middle element of each subarray as the root.

Here is my solution:

#include<iostream>
using namespace std;

struct Node
{
   int data;
   Node* left;
   Node* right;
};

Node* makeNode(int value)
{
   Node* temp = new Node;
   temp->data = value;
   temp->left = NULL;
   temp->right = NULL;
   return temp;
}
  

Node* buildTreeHelper(int nums[], int first, int last)
{
   if(first > last)
   {
       return NULL;
   }
   int middle = (first + last) / 2;
   Node *tree = makeNode(nums[middle]);
   tree->left = buildTreeHelper(nums,first,middle-1);
   tree->right = buildTreeHelper(nums,middle+1,last);
   return tree;
}

Node* buildTree(int nums[], int length)
{
   return buildTreeHelper(nums,0,length-1);
}

void print(Node* root)
{
   if(root == NULL)
   {
       return;
   }
   print(root->left);
   cout << root->data << " -> ";
   print(root->right);
}

int main()
{
   int vals[] = {1,5,3,2,9,6,8};
   int n = sizeof(vals)/sizeof(vals[0]);
   cout << "Given array: ";
   for(int i = 0; i < n; i++)
   {
       cout << vals[i] << " ";
   }
   cout << " Inorder traversal of balanced binary search tree: ";
   Node *root = buildTree(vals,n);
   print(root);
   cout << " ";
   return 0;
}

My solution is not correct because the array is not sorted. Can someone please fix this?

Explanation / Answer

I think the ouptut may be created in some changes in code

void print(Node* root)
{
   if(root != NULL)
     {print(root->left);
   cout << root->data << " -> ";
   print(root->right);}

    else{ return;}

}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.