edited by
10,931 views
43 votes
43 votes

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:

  1. B1: $(1+\text{height}(n \to \text{ right}))$; B2: $(1+\max(h1, h2))$
  2. B1: $(\text{height}(n \to \text{ right}))$ ; B2: $(1+\max(h1,h2))$
  3. B1: $\text{height}(n \to \text{ right})$ ; B2: $\max(h1, h2) $
  4. B1: $(1+ \text{height}(n \to \text{ right}))$ ; B2: $\max(h1, h2)$
edited by

3 Answers

Best answer
67 votes
67 votes

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

edited by
40 votes
40 votes

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.

edited by
4 votes
4 votes

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)

Answer:

Related questions

50 votes
50 votes
2 answers
2
gatecse asked Aug 5, 2014
13,293 views
The worst case running time to search for an element in a balanced binary search tree with $n2^{n}$ elements is$\Theta(n\log n)$$\Theta(n2^n)$$\Theta(n)$$\Theta(\log n)$
48 votes
48 votes
4 answers
4
go_editor asked Apr 21, 2016
13,579 views
Consider the following relations $A, B$ and $C:$ $$\overset{\textbf{A}}{\begin{array}{|c|c|c|}\hline\\\textbf{Id}& \textbf{Name}& \textbf{Age} \\\hline12& \text{A...