in DS
15,290 views
74 votes

A weight-balanced tree is a binary tree in which for each node, the number of nodes in the left sub tree is at least half and at most twice the number of nodes in the right sub tree. The maximum possible height (number of nodes on the path from the root to the furthest leaf) of such a tree on n nodes is best described by which of the following?

  1. $\log_2 n$
  2. $\log_{\frac{4}{3}} n$
  3. $\log_3 n$
  4. $\log_{\frac{3}{2}} n$
in DS
15.3k views

11 Comments

I tried to solve this question for different values of n :

n=4 maximum height 2

n=7 maximum height 4

n=13 maximum height 8

but none of the above options satisfy the above cases

PLEASE HELP
3
can somebody explain it diagramatically ?????? and also simplify the recuurance relation plz......
0

The number of nodes in the left sub tree is at least half and at most twice the number of nodes in the right sub tree
There n nodes in the tree, one node is root now (n-1) nodes are left. to get the maximum height of the tree we divide these (n-1) nodes in three parts each of size $\frac{n-1}{3}$ 
Now keep two parts in LST and one part in RST. 
LST = $2*\frac{n-1}{3}$, and
RST=$\frac{n-1}{3}$
Now we can see that LST is multiplied by 2 means this part of the tree will cause the max height of the tree. which is log3/2(n).
Hence, answer is (D).

33
why we divides in three parts  

ehy not two, one for left and second for right
0

@ Manu Thakur , 

Please show the procedure to get the final result from your method, im  unable to get here.

0
I used the log calculator and figured out the answer but don't know if in gate calculator we have option .to find log value for base x
0
Because the left part is 2 times the right part, so if you divide the (n-1) part into 3 parts (/3) you can have 2 for the left and one for the right !
0

@ how can u get the final answere,please derive.

0

HOW DID YOU GET THE ANSWER USING CALCULATOR ? CAN YOU PLEASE ELABORATE ?

0
(C) if minimum height of the tree was asked
1

4 Answers

90 votes
 
Best answer

Let  $n_l$ and $n_r$ nodes be present in the left and right sub-trees respectively.

We have, $\frac{n_r}{2}\le n_l \le 2n_r$. Without loss of generality, let the left sub-tree have greater number of nodes $(2n_r\ nodes)$. Then, $n_r + 2n_r + 1 = n$. Thus we get, $n_l = {2(n-1) \over 3}$ and $n_r = {n-1 \over 3}$.

Total number of nodes can be described by the recurrence:

$T(n) = T\left(\frac{n-1}{3}\right) + T\left(\frac{2(n-1)}{3}\right) + 1 \text{ and }  T(1) = 1$

As this makes maximum nodes go to one subtree and that is what we want to get the maximum height with a given number of nodes.

Now, the height of the tree will be: $H(n) = H(\frac{2}{3}(n-1)) + 1$ and $H(1) = 1$

We can draw a recurrence tree and the cost at each level is 1, and the height will be $\color{red}{\log_{\frac{3}{2}}(n)}$.
So, D option is the answer.

edited by
by

21 Comments

Great, thank you sir :-)
0
Sir, Can you please explain me how did you get /3 (div by 3)?
0

See...here total number of node is n.... subtract 1 as root node . now nodes are - n-1

These n-1 divided in such a way that left ubtree is half or double as much as right subtree. So technically we are parting n-1 in 3 equal set. 2 set goes to  left/right nd rest tp its sibling.

T(n) = T((n-1)/3)) + T(2(n-1)/3) + 1

now which ever child have 2(n-1)/3  nodes would be counted for height calculation. 

so

H(n)=H(2(n-1)/3)+1

2
How the base case is H(1)=0. Won't it be equal to 1 since height of the tree containing single node is 1?
1
No, height of a tree containing a single node = height of a leaf node = 0 by the general trend unless mentioned otherwise.
0
sir please give an example tree which satisfy the reccurrance relation   T(n) = T((n-1)/3)) + T(2(n-1)/3) + 1
0
@Arjun Sir, here T(n) = T((n-1)/3)) + T(2(n-1)/3) + 1, if T(n) is total number of nodes then what is n ?
6
^I'll approximate them to Master Theorem form and get upper and lower bounds. If both are asymptotically same, then we are done. Else, require other method.
0
please help to how this recursive equation build?????? any easy way
0
I got somewhat . But could u explain it more clearly ?
0
I am not getting excatly why (n-1)/3 instead of 2 and also why (n-1 ) nodes?
0
reshown by

how tree of 2 node is possible?? in this case one subtree contain 1 node and another contain 0 node which is not double not half ?  according to me only balanced binary tree is possible in this case which take log(2)n time.

1

Arjun sir how u find this recurrence relation?

0

@Arjun Sir, it would be really helpful to add the fact that : 


Let  $n_l$ and $n_r$ nodes be present in the left and right sub-trees respectively.

We have, $\frac{n_r}{2}\le n_l \le 2n_r$. Without loss of generality, let the left sub-tree have greater number of nodes $(2n_r\ nodes)$. Then, $n_r + 2n_r + 1 = n$. Thus we get, $n_l = {2(n-1) \over 3}$ and $n_r = {n-1 \over 3}$.

1
Please add as an answer.
1
@Arjun sir

1.Can you please suggest the approach we should tackle this type of problem and to make recurrence relation.

2.Any links to practice these type of problem to gain confidence.

 

Thanks
0
I think in order to get Max height ,we should have min no of nodes ,so here we should nodes in lst to be x/2 if x= no of nodes in right subtree ,then also division will be n-1 to be n-1/3 and 2n-1/3 like n-1= 12 then x=8 and lst  have 4 so 4/12 = n-1/3 and other has 2n-1/3
0

@Arjun Sir,

A small technical correction in the answer : 

height, in the question, is defined to be number of nodes on the path from the root to the furthest leaf. 

So, H(1) = 1.

Base case won't be H(1) = 0

1
Thanks šŸ˜Š
0
sir, by solving the recurrence relation of height i am getting 1+log(base 3/2) (n-1), not the exact log(base 3/2), i am getting H(n)=H((n-1)/(3/2)^k)+k when getting for n=k, is it correct
0
100 votes

Ans: D

8 Comments

@marcusD are you considering number of nodes to be n+1?
2
nice explanation
2
Iā€™m still confused. The division should be 2(n-1)/3 and (n-1)/3, I guess. have you consider n-1 as n only?
1
why solving for k equation is equated to 1??
0
He/She has assumed that on continuously giving maximum nodes to right subtrees at every point we will reach a state such that we will be left with just one node in right subtree thus number of nodes in right subtree is equated to one ā€¦.by the way this answere deserves best answere.
0
you are dividing n into n/3 and 2n/3. But the parent node also uses 1 count from n.

So it must be 2(n-1)/3 and (n-1)/3

Why it is like that?
0
amazing explanation. Thanks!
1
@marcusD your explantion is wonderful,Thanku so much
0
26 votes

we can make tree either Right skewed or left skewed.

2 Comments

@Nitesh Singh 2 why use n after n/3 and 2n/3... and in last (3/2)^k can you please explain?

0
Nicely explained!
0
1 vote

The number of nodes in the left sub tree is at least half and at most twice the number of nodes in the right sub tree. 
Let assume number of nodes in right subtree is r and for left subtree number of nodes are l.

then for left subtree number of nodes ranges from ..

 $r/2\leqslant l\leq 2r$

and root contains 1 node. 

         root node+ left subtree nodes+ right subtree nodes= n

So,      1+r/2+r = n

             3r/2 = n-1

              r=  $2(n-1)/3$

Now, why we use r/2 because we want our tree to be maximum possible height that can only possible when we take minimum number of nodes.

LST = $(n-1)/3$

RST = $2(n-1)/3$

Now we can see that RST is multiplied by 2 means this part of the tree will cause the max height of the tree. which is log3/2(n).
Hence, answer is (D).

 

Answer:

Related questions