Imagine that our familiar class Node has a mysterious member function g () which

Question

Imagine that our familiar class Node has a mysterious member function g () which is defined as follows. int Node :: g() { if (! left Child and ! rightChild) return 1: if (leftChild and !rightChild) return 1 + leftChild rightarrow g(): If(! leftChild and rightChild) return 1 + rightChild rightarrow g(): int lft = 1 + leftChild rightarrow g(): int rgt = 1 + rightChild rightarrow g(): if (lft rightarrow = rgt) return lft: else return lft: else return rgt: } What does member function g() compute? (a) The number of leaf nodes in a binary tree rooted in the calling Node (b) The total number of nodes in a binary tree rooted in the calling Node. (c) The depth of the binary tree rooted in the calling Node. (d) The number of left and right subtrees of the binary tree rooted in Node.

Explanation / Answer

int Node<T>::g() {
   if (! leftChild and IrightChild) //if the node is leaf
       return 1;
   if (leftChild and !rightChild) //if right child is null
       return 1 + leftChild->g();
   if (!leftChild and rightChild) //if left child is null
       return 1 + rightChild->g();

//remaining part is executed if both subtrees are not empty

int lft = 1 + leftChild->g();
int rgt = 1 + rightChild->g();
if (lft >= rgt)
return lft;
else
return rgt;

------------------------------------------------------
If we look into the first three if statement, we see that the function adds 1 and call itself through its child node when possible. This is true only when the node have a null subtree attached to it.

Now if we look into the 2nd part, we can say that the function adds 1 to itself and calls itself through its child node. The only differece is in this step we compare the value of g() from both the sub-trees and return the max of both.

So in short:
   i) If a node has one child, the function adds 1 and goes to a lower level and continues this till it reaches a leafnode.
   ii) if the node has 2 child, it add 1 to g() return value of both the subtree(goes a level lower) and returns the max among them.

   So if we study the conclusion we can say that the steps in this method is talking of height of the tree.

So this function calculates the depth of a particular node and option c is correct

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---