GATE CSE 2012 | Question: 47

Question

The height of a tree is defined as the number of edges on the longest path in the tree. The function shown in the pseudo-code below is invoked as height (root) to compute the height of a binary tree rooted at the tree pointer root.

int height(treeptr n)
{ if(n == NULL) return -1;
  if(n -> left == NULL)
     if(n -> right == NULL) return 0;
     else return B1; // Box 1
  
  else{h1 = height(n -> left);
       if(n -> right == NULL) return (1+h1);
       else{h2 = height(n -> right);
            return B2; // Box 2
            }
       }
}

The appropriate expressions for the two boxes B1 and B2 are:

• A. B1: $(1+\text{height}(n \to \text{ right}))$; B2: $(1+\max(h1, h2))$
• B. B1: $(\text{height}(n \to \text{ right}))$ ; B2: $(1+\max(h1,h2))$
• C. B1: $\text{height}(n \to \text{ right})$ ; B2: $\max(h1, h2) $
• D. B1: $(1+ \text{height}(n \to \text{ right}))$ ; B2: $\max(h1, h2)$

Comments

In tree many variation of question can be asked like count no of internal nodes,no of leaf nodes,no of nodes which has only left child or right child , no of nodes with degree 2 and many more.

So next question how can we answer such problems??

so generally code  will be given to us and they would left some blank space and out of given option we have to fill the blank space .

the best approach i can find as of now for verifying option  is Stack method .  In Tree generally node would be called preorder and execution will done postorder. So start running the code by  pushing  root (by taking a simple example)in stack it and and also keep in mind where you have gone to call next node (line no) continue this push and pop operation until  you get the asked value.

if any one is having any other  approaches​​​​​​ then ...please share

---

Assumption: You have the required background knowledge of trees, recursion and stack.

---

We're using recursion to cut down our problem into smaller parts.

Height of a tree would be equal to height of it's immediate left or right subtree (whichever's maximum) + 1.

Now, that subtree can be treated as a tree in itself, and we call the function recursively with the root of this subtree as the tree.

This process goes on until we reach leafs.

We know that height of a leaf = 0.

So, we return from this recursive call, and keep adding the 1's that we encountered in our stack while placing those recursive calls. This fetches us the height.

Clearly, Option A.

---

TIP: Place the curly brackets after if and else wherever it is not placed. This might help you in knowing which particular else is associated with which particular if condition and then analyze the code.

This might save you from some confusion :)

 

 

 

Answer 1

Answer is option A.
From the diagram below we are able to see how this works :

Comments

worst explaination

---

agree with @rohit9

---

@BILLY yes bro , the 1 is added for the root node . 

Answer 2

I got a hint ; How to quickly approach this type of question :--In this type of questions where we already know we want to find something(i.e. Height ) then simply draw min possible tree which reach us upto the Given Boxes.

For Box1,Box2  tree will be as given in below img :-->

Now Analyse the code for above trees we get Option A as Ans.

Comments

didn't understood your logic???

Answer 3

1st if condition is true only if there is no node in binary tree.

2nd if condition told if there is only 1 node in the tree.Then height of tree is 0.

Now,

if the tree has at least one left node, then it is going to calculate B2

otherwise, if the tree has  only right subtree, tree height calculated by B1 only

B1= right subtree+1 to get height of the tree

Now, h1= height of right subtree of a node

h2= height of left subtree of a node

height of a tree= 1+ max(h1,h2)

Comments

Leaf node is taken as at zero height therefore addition of one will be there to make height one

---

@smartmeet I think 1 is added in statement

height of a tree= 1+ max(h1,h2)

because of this condition 

if(n == NULL) return -1;

if it was 

if(n == NULL) return 0;

then we would not have required extra 1. the following would just have worked fine

height of a tree= max(h1,h2).

---

that's the condition for dangling pointer.... it doesn't matter if it's -1 or 0,
the actual reason we've added 1 is for the root node left subtree and the right subtree count.