1.9k views

Suppose you are given a binary tree with n nodes, such that each node has exactly eiter zero or two children. The maximum height of the tree will be

1. $\frac{n}{2}-1$
2. $\frac{n}{2}+1$
3. $(n-1)/2$
4. $(n+1)/2$
in DS
recategorized | 1.9k views
0
In GATE question they mention the definition of height. Here nothing is mentioned so maybe we can take the height of level 0 as zero.

Question is about full binary tree..

If it is left or right biased than gives the maximum height...

Maximum height is( n-1/ 2) taking root at height 0.
by Boss (25.3k points)
selected
0
but if we take height at 1,  ans will be D...so which one is correct ? and why ? plzz clarify me
0
Height of the tree is equal to largest level of the Tree.
Given Tree is a strictly binary tree, having either 0 or 2 children

such trees always contains odd number of nodes

if n=5, then max height will be 2 which is (n-1)/2

if n=7, then max height will be 3 which is again (n-1)/2

by (293 points)
+1 vote

Ans is option C)

by (195 points)

1
2