Define Abstract Data type (ADT) Use the following class for problems 2 and 3: pu

Question

Define Abstract Data type (ADT) Use the following class for problems 2 and 3: public class BinSearchTree {private Node root; private class Node {T data; Node left, right;; public Node(T t) {data = t;}//get and set methods for all three fields are here}} Write a method: void showHighLow() which prints out the highest and lowest values in the tree (or an appropriate message if the tree is empty) without traversing the entire tree. What is computed by the following method? public int screech(Node p) {if (p -- null) return -1; int 1 = screech(p.getLeft()); int r = screech(p.getRight ()); if (1 >= r) return 1 + 1; else return r + 1;}

Explanation / Answer

Abstract Data Type is a way to specify the components of a class : the data as well as the operations to operate on that data, but without giving the implementation. This also means information hiding concept.

For the questions 2, we will use characteristics of binary search tree.

Here, the method void showHighLow() is printing the highest and lowest value.

This is a binary search tree. So, it has a property saying all the nodes having less value than the root will be its left side and the values greater than the root node will be in its right sub-tree.

So, to find the smallest value from the tree, we need to go to left sub-tree's leftmost node and to find the largest value, we need to go to the rightmost node. So, this is the required task as this will not do the complete traversal of the tree as asked in the question.

So, the required method can be written as :

void showHighLow()
{

   if(root == NULL)
   {
       cout << "The tree is empty";
   }

   else
   {
       Node<T> node = root;

       while(node.getLeft() != NULL)
           node = node.getLeft();

       cout << " The minimum value is : " << node.getData();

       node = root;

       while(node.getRight() != NULL)
           node = node.getRight();

       cout << " The maximum value is : " << node.getData();
   }
}

Here, the getter and setter methods are not written in the class but I have implemented this using all getter methods because in the next question, the getter methods are used for the node class object. This means that these methods are available to use so I used it. So the implementation is same as I wrote. First it checks whether root node is present or tree is empty. If it is empty, then that is displayed. Or the things done are...
Start with root, go to leftmost which means till there is a node in left side. The leaf node will have null in its next so loop will be finished there. Then the leaf leftmost node is found and its data I printed. As this method's return type is void, it won't return anything, so you need to display it in the same function. The similar procedure goes on for the right and to find the maximum value.

Question 3 is to give the output of the given screech() method.

This method is doing what.. it is taking the node, then calling this function for its left node and its right node recursively and then till it is getting null which means the leaf node is encountered then for that leaf node when this function is called on its left and right, it will get -1 and returned so after that 1 is added and that value is passed on the upper level after processing 1 node completely. This process is adding 1 for every node on its left and its right and takes the maximum of both, then adds 1 to it, and which means the height of the sub-tree is found. This calculation goes on till root node and the final value returned by this function is the height of the tree.

If it is 0, that means there is only a root node in the tree. If it returns 1, it means this tree has 2 levels, and so on..

For example, take an example below:

n1
/
n2 n3
|
n4

screech() is processed as :

Note: screech(null) returns -1.

screech(n1) : It is not null so go after the if part, l = screech(n2) , r = screech(n3)

screech(n2) : not null so l = screech(null), r = screech(null) which means both l = r = -1 then screech(n2) returns -1 + 1 = 0
screech(n3) : not null so l = screech(null), r = screech(n4) so l = -1 , r = 0 same as n2 so max is r then 0 + 1 = 1 is returned by n3.

For n1, l = 0 and r = 1 so the max between these two is 1. So, the value to be returned is 1 + 1 = 2, which is the height of this tree.

Height = 0 means 1 level i.e. only root node
Height = 1 means 2 levels

In general, height = h means (h+1) levels.

So, in a nutshell, this method returns height of the given tree.

Please comment if there is any query. Thank you. :)

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

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