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

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?

- $\log_2 n$
- $\log_{\frac{4}{3}} n$
- $\log_3 n$
- $\log_{\frac{3}{2}} n$

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 **log _{3/2}(n)**.

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.

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

@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}$.

@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

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

Search GATE Overflow