Binary Search Tree (14 points) Recall that in a binary search tree, each node is defined...

Transcribed Image Text:

Binary Search Tree (14 points) Recall that in a binary search tree, each node is defined as follows. struct node { int key; node *left; node *right; node *parent; \ Other data *\ } Recall that in a binary search tree, at every node, the key at a node is larger than or equal to the keys in its left subtree, and is smaller or equal to the keys its right subtree. In each case below, write a procedure in a C-like language that achieves the required task. (a) (3 pt) Compute the sum of all the keys in the binary tree. int Sum (node* root) { (b) (3 pt) Given a <b, compute the sum of all keys in the tree falling within the range [a..b]. If there is no key in the given range, return 0. int SumRange (node* root, int a, int b) { (c) (4 pt) Given a <b, return the pointer to a node having the maximum key in the range [a..b]. If there is more than one such node, return the node that appears the latest in the inorder traversal. If there is no such node, return the NULL pointer. node MaxRange (node* root, int a, int b) { (d) (4 pt) Given integers a and b, perform a linear transformation au bon all keys in the tree, i.e., if a node has key value v originally, the new key value should be au ib. The new tree must also be a binary search tree. The method should return the pointer to the root of the new tree. node Transform (node* root, int a, int b) { Binary Search Tree (14 points) Recall that in a binary search tree, each node is defined as follows. struct node { int key; node *left; node *right; node *parent; \ Other data *\ } Recall that in a binary search tree, at every node, the key at a node is larger than or equal to the keys in its left subtree, and is smaller or equal to the keys its right subtree. In each case below, write a procedure in a C-like language that achieves the required task. (a) (3 pt) Compute the sum of all the keys in the binary tree. int Sum (node* root) { (b) (3 pt) Given a <b, compute the sum of all keys in the tree falling within the range [a..b]. If there is no key in the given range, return 0. int SumRange (node* root, int a, int b) { (c) (4 pt) Given a <b, return the pointer to a node having the maximum key in the range [a..b]. If there is more than one such node, return the node that appears the latest in the inorder traversal. If there is no such node, return the NULL pointer. node MaxRange (node* root, int a, int b) { (d) (4 pt) Given integers a and b, perform a linear transformation au bon all keys in the tree, i.e., if a node has key value v originally, the new key value should be au ib. The new tree must also be a binary search tree. The method should return the pointer to the root of the new tree. node Transform (node* root, int a, int b) {

Answer rating: 100% (QA)

Let us see the procedures in a Clike language a Compute the sum of all keys in the binary tree int S... View the full answer