The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+3 votes
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 by Veteran (100k points)
recategorized by | 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.

3 Answers

+3 votes
Best answer
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 by
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.
+2 votes
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

So, answer is C
by (293 points)
+1 vote

Ans is option C)

by (195 points)

Related questions

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
50,092 questions
55,237 answers
190,755 comments
85,990 users