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

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$
asked in DS by Veteran (59.5k points) | 4.3k views
0
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
0
can somebody explain it diagramatically ?????? and also simplify the recuurance relation plz......
+4

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).

0
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

3 Answers

+49 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) = 0$

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.

answered by Veteran (357k points)
edited by
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 ?
0
^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

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.

0

Arjun sir how u find this recurrence relation?

+1

@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.
0
@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
+7 votes

Ans: D

answered by (97 points)
0
@marcusD are you considering number of nodes to be n+1?
+1 vote

we can make tree either Right skewed or left skewed.

answered by (239 points)


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

39,828 questions
46,802 answers
140,987 comments
58,943 users