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