**Problem Link:**

Contest

Practice

**Author:** Rajat De

**Testor:** Aman Kedia

**Editorialist:** Rishav Pati

**Difficulty:** Easy - Medium

**Topics:** Basic Combinatorics, Recusive Functions

**Problem:-**

Given a number n which is of the form 2^x - 1 or 2^x - 2 Find the number of permutations of [1 , n] such that when inserted into a binary search tree from leftmost element of the permutation to rightmost element of the permutation, the tree obtained is Balanced (It has a height of ceil(log(n + 1))).

Constraint: 1 \le n \le 10 ^ 6.

**Quick Explanation:-**

If f returned the answer when n is of the form 2^x - 1 and g when n is of the form 2^x - 2 then,

and

**Explanation:-**

First notice that the maximum number of nodes a tree of height x can have is 2^x − 1.

So when n is of the form 2^x − 1 for some x, the height of the tree should be exactly x and

hence height of each subtree of each child of the root should be at most x − 1.

So, each of the 2 subtrees attatched to the root contain at most 2^{x−1} − 1 nodes.

But our tree contains 2^x − 1 nodes which is (2^{x−1} − 1) + (2^{x−1} − 1) + 1.

This means that each of the subtree contains exactly 2^x − 1 nodes.

This leaves the median node to be the only plausible choice for the root.

Now suppose we have a function f([1, 2, 3, ..., k]) which tells us the number of permutations

of [1, 2, ..., k] which form a balanced binary tree.

Then, we want to find out the value of f([1, 2, 3, ..., n]).

Now, under the condition that n is of the form 2^x − 1, our root is fixed. Which means that

the first number of all the valid permutations are fixed. Call this number as r.

The left subtree of r will have the numbers [1, 2, 3, ..., r − 1] while the right subtree will

have the numbers [r + 1, r + 2, r + 3, ..., n].

Since these are independent sub problems, we can solve them separately by calling f([1, 2, 3, ..., r−
1]) and f([r + 1, r + 2, r + 3, ..., n]).

Now notice that since the actual values on the nodes do not matter and only the relative

ordering between nodes matter, any increasing sequence of n numbers is essentially same as

the sequence [1, 2, 3, ..., n]. So, we can replace the entire sequence with a single number n.

So the answer for both subtrees will be f(n/2). (Notice here that n/2 will also be of the

form of 2^x − 1.)

Now, we need to use this result to build a valid permutation for the original problem.

In the first position of any valid permutation, we have r. In the rest n − 1 places, n/2 places

are for the numbers which go in the left sub-tree and n/2 places for the numbers which go

in the right sub-tree.

There ^{n−1}C_{n/2} ways of choosing these positions.

Hence,

Now, when n is of the form 2^x − 2 we essentially have 2 choices for the root node.

Pick any of them in 2 ways. This leaves one of the subtree with n/2 elements and one of the

subtree with n/2 − 1 elements.

Notice that n/2 here is of the form 2^x − 1 and n/2 − 1 is of the form 2^x − 2.

So, if the answer in this case is given by a function g(n), we have:

It should be clear that a simple recursive implementation for f will return the answer for n

in O(logn) time.

And g(n) will, in each level, invoke f once and g once with the parameter value roughly

halved.

Since f will take O(logn) time and there will be at most O(logn) invocations, overall complexity

of a simple recursive implementation will be just O(log^2n).