3.9k 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 | 3.9k 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

+2
0
can somebody explain it diagramatically ?????? and also simplify the recuurance relation plz......
+2

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

0
why we divides in three parts

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

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

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.

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