Binary Tree Maximum Possible Height

[Lelouch_Lamperoug]

Please explain the solution

[Ruturaj]

T(n) = T(n-1/3) + T(2(n-1/3)) + 1

This is the recurrence relation so formed.

Now maximum height will be in the part T(2(n-1)/3) as it will go to deeper depth than T((n-1)/3)

So,
H = H(2(n-1)/3) +1
H(1) = 0

Solving we get, option D as answer.

[shreya]

In which part u get the highest height left subtree or right subtree

[Ruturaj]

In question it’s written, “The number of nodes in the left subtree is atleast half and atmost twice the number of nodes in the right sub tree”

This line is important.
case 1: suppose left subtree has half the number of nodes in the right sub tree.

Then in this case the equation would be,
T(n) = T((n-1)/3) + T(2(n-1/3)) + 1

T((n-1)/3) signifies no of nodes on left part and
T(2(n-1/3)) signifies no of nodes on right part.

So in this case height will be determined by right subtree.

case 2: suppose left subtree has twice the number of nodes in the right subtree.

Then in this case the equation would be,
T(n) = T(2(n-1)/3) + T((n-1/3)) + 1

T(2(n-1)/3) signifies no of nodes on left part and
T((n-1/3)) signifies no of nodes on right part.

So in this case height will be determined by left subtree.

The maximum one will always go to deeper depth and hence determine the height.
In our case T(2(n-1)/3) > T((n-1)/3)
so it will always go to deeper depth and hence determine the height.