23,090 views
101 votes
101 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$

7 Answers

2 votes
2 votes

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

 

0 votes
0 votes
I think there isn’t a need of doing all the calculations for this question….

for a balanced search tree which takes n/2 elements on left and right subtrees ,

for such a tree with n(1/2) elements the height of the tree H=log n base 2 for (1/2)n elements

similarly in this case the left subtree contains (2/3)n elements and right subtree contains (1/3)n elements

so the height of the tree would be the height of the left subtree i.e, H=log n base 3/2 for (2/3)n elements..
Answer:

Related questions

20 votes
20 votes
1 answer
1
Kathleen asked Sep 15, 2014
2,501 views
Draw all binary trees having exactly three nodes labeled $A, B$ and $C$ on which preorder traversal gives the sequence $C, B, A$.
35 votes
35 votes
5 answers
2
Kathleen asked Sep 15, 2014
30,808 views
The number of leaf nodes in a rooted tree of n nodes, with each node having $0$ or $3$ children is:$\frac{n}{2}$$\frac{(n-1)}{3}$$\frac{(n-1)}{2}$$\frac{(2n+1)}{3}$
23 votes
23 votes
2 answers
4
Kathleen asked Sep 15, 2014
5,037 views
Minimum sum of product expression for $f(w,x,y,z)$ shown in Karnaugh-map below $xz + y'z$$xz' + zx'$$x'y + zx'$None of the above