Problems to be handed in. Please submit each problem on a separate sheet of pape

Question

Problems to be handed in. Please submit each problem on a separate sheet of paper. Give algorithms for implementing the following operations on a binary search tree: (a) Average-Keys: Given a node x, returns the average value of the keys in the subtree rooted at x. For full credit your procedure should run in O(n) time. (b) Range Search: Given an interval [a, b] and a tree T, returns a list of all the nodes with keys in the range a, b. There is an easy theta (n) solution, but for credit your algorithm should run in time O(k + h) where k is the number of nodes in the range and h is the height of the search tree. Analyze the running time of your algorithm carefully. Remember that some of the homework grade is for the clarity of your explanation.

Explanation / Answer

(a)

nt average_keys(node* root,int* sum)//this function returns the number of nodes in the tree
{
if(node==null)
return 0;
int lsum=0;
int rsum=0;
int countleft =average_keys(root->left,&lsum);
int countright = average_keys(root->left,&rsum);
*sum = lsum +rsum;
return countleft + countright;
}
float findaverage(node *root) //it return average of all the nodes
{
int sum=0;
int count = average_keys(root,&sum)
return float(sum)/float(count)
}

The time complexity of above algorithm is O(n) because it traverse all the nodes once

(b)

vector<int> arr;
void range_search(int a,int b,node* root)
{
if(root==NULL)
return;
if(root->data <a)
return range_search(a,b,node->right);//go to right of subtree
else if(root->data > b)
return range_search(a,b,node->left);//go to the left of subtree
else
arr.push_back(node->data); //add data into the list
range_search(a,b,node->right);
range_search(a,b,node->left);
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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