CPSC 131-03 Final Exam VI. (21 points) Binary search tree code write a binary tr
ID: 3840936 • Letter: C
Question
CPSC 131-03 Final Exam VI. (21 points) Binary search tree code write a binary tree member function, int the Binary sear returns difference in Tree KEY Difference (KEY k), that computes and of an height of the children of the node containing Note that the height a given key external node is o; erwise, the height is height of children. For example, the 1 maxim for following return 1. Difference (10) should return 2 tree. 10 15 Partial definitions of a BinarysearchTree class and its related TNode class are shown in the next pages. This is a simpler version of the code shown in class. In particular: all members of TNode are public (TNode is a struct), a TNode stores only a key (the template type), the nodes have no parent pointers, there is no Position class (use pointers directly), and external nodes can store values, You may use loops or recursion as needed. If necessary, you may add private helper function(s) Do not make changes to any of the existing functions. Space to write your new function(s) is given in the end. template struct TNode a node of the tree element value E elem; TNode *left; left child. TNodexE right; right child TNode KE elem left (NULL right (NULL) default constructor TNodeExplanation / Answer
template <typename KEY>
int BinarySearchTree<KEY> : :heightDiffarance (KEY k) {
TNode<KEY> *node = find(k);
int max = getMaxHeight(node);
int min = getMinHeight(node);
return max - mim
}
template <typename KEY>
int BinarySearchTree<KEY> : :getMaxHeight (TNode<KEY> *node) { //reccursion to return the max height from leaf node to given node
if (node == NULL)
return 0;
if (node -> left == NULL && node->right == NULL) //if leaf node return 0
return 1;
int left = getMaxHeight (node->left); //get max height of left tree
int right = getMaxHeight (node->right); //get max height of right tree
return (left>right?left:right) + 1; // add 1 to the max height and return
}
template <typename KEY>
int BinarySearchTree<KEY> : :getMaxHeight (TNode<KEY> *node) {
if (node == NULL)
return 0;
if (node -> left == NULL && node->right == NULL)
return 1;
int left = getMaxHeight (node->left);
int right = getMaxHeight (node->right);
return (left>right?right:left) + 1;
}
I hope this code helps you, Let me know if you need any assistance on this code.