Please explain the solution

# Binary Tree Maximum Possible Height

**Ruturaj**#2

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.

**Ruturaj**#4

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.