23,061 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

Best answer
114 votes
114 votes

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
135 votes
135 votes

Ans: D

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,807 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,035 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