The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+21 votes
1.9k views

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.

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)$
asked in DS by Veteran (358k points)
edited by | 1.9k views

3 Answers

+22 votes
Best answer

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

 

answered by Boss (30.8k points)
edited by
0
is that 1 is added for the root node ?if not plz explain @ arjun sir
0
this is a great explanation @amarVashisth
+25 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.

answered by Boss (22.9k points)
edited by
0
didn't understood your logic???
+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)

answered by Veteran (98.3k points)
0
Why added '1' in th final calculation, can't understand!
+1

h1 is height of left subtree and h2 height of right subtree.

Now, to get total height of tree we have to add root with max (left subtree, right subtree) of the tree.

got it?

0
Actually

if u take 3 node tree(as shown in @Rajesh answer h1 and h2 returning 0, So, there to get height we have to take 1+max(h1,h2)=1+0=1)
0
Leaf node is taken as at zero height therefore addition of one will be there to make height one


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

40,845 questions
47,506 answers
145,764 comments
62,261 users