It has been raining all day in the Twin Cities of Minneapolis and St. Paul. The good thing is that there has been little lightning. I was going to replace an old UPS that I am using to power my main computer in which I develop all the code for this blog, but it was not necessary. I will replace the UPS over the weekend.
I selected LeetCode 96 Unique Binary Search Trees problem. I looked for problems with the binary search tag and this one came up. That said I did not see the use of the binary search technique. Perhaps the problem was not properly classified.
Given an integer n, return the number of structurally unique BST's (binary search trees) which has exactly n nodes of unique values from 1 to n. Constraints: o 1 <= n <= 19
By reading the requirements it might seem that the problem has to do with binary search trees. By spending a few more on the requirements, the problem has to do more with combinations.
I understand that no one knows everything about solving problems like the ones presented by LeetCode or any other similar website. In an interview one might not be allowed to search the web to gather information. That is not how software developers / engineers or system architects work. We consult the web and books. In this case that is what I did.
I ran into something called Catalan number. I know about the Catalan language and have been a few times in Barcelona, Spain which is in the region of Catalonia.
Catalan numbers are a sequence of natural numbers that occur in many interesting counting problems like following: 1. Count the number of expressions containing n pairs of parentheses which are correctly matched. For n = 3, possible expressions are ((())), ()(()), ()()(), (())(), (()()). 2. Count the number of possible Binary Search Trees with n keys. 3. Count the number of full binary trees (A rooted binary tree is full if every vertex has either two children or no children) with n + 1 leaves. 4. Given a number n, return the number of ways you can draw n chords in a circle with 2 x n points such that no 2 chords intersect.
It seems that Catalan numbers is a sequence that occurs in many counting problems. There are many applications but take a look at item #3 in the previous list. In addition I found on-line Applications of Catalan Numbers and most important Program for nth Catalan Number. I read the articles listed in this post and then started experimenting.
public int numTrees(int n) {
}
Getting back to the problem at hand, we are given a number of nodes and we need to return the number of different binary search trees we can generate or deduct. Spoiler alert: there is no need to generate a single binary search tree. The signature for the function of interest receives the number of nodes and the function should return the number of combinations.
3 main <<< n: 3 main <<< catalan0(0): 1 main <<< catalan0(1): 1 main <<< catalan0(2): 2 main <<< catalan0(3): 5 main <<< catalan(0): 1 main <<< catalan(1): 1 main <<< catalan(2): 2 main <<< catalan(3): 5 main <<< numTrees: 5 1 main <<< n: 1 main <<< catalan0(0): 1 main <<< catalan0(1): 1 main <<< catalan(0): 1 main <<< catalan(1): 1 main <<< numTrees: 1 13 main <<< n: 13 main <<< catalan0(0): 1 main <<< catalan0(1): 1 main <<< catalan0(2): 2 main <<< catalan0(3): 5 main <<< catalan0(4): 14 main <<< catalan0(5): 42 main <<< catalan0(6): 132 main <<< catalan0(7): 429 main <<< catalan0(8): 1430 main <<< catalan0(9): 4862 main <<< catalan0(10): 16796 main <<< catalan0(11): 58786 main <<< catalan0(12): 208012 main <<< catalan0(13): 742900 main <<< catalan(0): 1 main <<< catalan(1): 1 main <<< catalan(2): 2 main <<< catalan(3): 5 main <<< catalan(4): 14 main <<< catalan(5): 42 main <<< catalan(6): 132 main <<< catalan(7): 429 main <<< catalan(8): 1430 main <<< catalan(9): 4862 main <<< catalan(10): 16796 main <<< catalan(11): 58786 main <<< catalan(12): 208012 main <<< catalan(13): 742900 main <<< numTrees: 742900
Since we will be developing this code in Java using the VSCode IDE on a Windows computer, and not in the on-line IDE provided by LeetCode, we will need to generate test code to collect the input, call the function in question and display the result. Note that the test code IS NOT PART OF THE SOLUTION.
The first and only input line represents `n` which is an integer passed to the function of interest. Our test code generated and populates the variable `n` and displays it. We do this to make sure that all is well so far.
It seems that the code call makes a set of calls to a couple functions which seem to return the same values when called with the same argument. Note that in the first example, we are given `n` with a value of 3 and the last output for each function returns the proper answer for our problem.
Our test code then makes a call to the function of interest and returns a result which is then displayed.
You might wish to take a look at the other examples.
/**
* Test scaffold.
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read `n` ****
int n = Integer.parseInt(br.readLine().trim());
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< n: " + n);
// ???? ????
for (int i = 0; i <= n; i++)
System.out.println("main <<< catalan0(" + i + "): " + catalan0(i));
// ???? ????
for (int i = 0; i <= n; i++)
System.out.println("main <<< catalan(" + i + "): " + catalan(i));
// **** call function of interest and display result ****
System.out.println("main <<< numTrees: " + numTrees(n));
}
Our test code seems to match very closely to the description of processing a test case. We can see that the `catalan0()` and `catalan()` functions are called out of the context of our problem. This was done to get familiar with them.
The last line invokes the function of interest and displays the results.
/**
* Compute the specified catalan number.
* This is a recursive call.
*
* Runtime: 1960 ms, faster than 8.41% of Java online submissions.
* Memory Usage: 35.6 MB, less than 77.23% of Java online submissions.
*/
static int catalan0(int n) {
// **** base case ****
if (n <= 1) return 1;
// **** initialization ****
int res = 0;
// **** recursive calls ****
for (int i = 0; i < n; i++)
res += catalan0(i) * catalan0((n - 1) - i);
// **** return result ****
return res;
}
This function generates the Catalan number associated with the specified `n` argument. It is a recursive call. Note that it is a little heavy and prone to recalculating values.
I made name modifications and submitted it as the function of interest. The results are in the comment section of the function. Slow but it was accepted.
/**
* A Binomial coefficient based function to find the
* nth catalan number in O(n) time.
*
* Runtime: 0 ms, faster than 100.00% of Java online submissions.
* Memory Usage: 35.8 MB, less than 49.43% of Java online submissions.
*/
static long catalan(int n) {
// **** calculate value of 2nCn ****
long c = binomialCoeff(2 * n, n);
// **** return 2nCn / (n+1) ****
return c / (n + 1);
}
This is the second implementation of the Catalan number function. We calculate a binomial coefficient and return it divided by `n + 1`.
/**
* Returns value of Binomial Coefficient C(n, k)
*/
static long binomialCoeff(int n, int k) {
// **** initialization ****
long res = 1;
// **** since C(n, k) = C(n, n-k) ****
if (k > n - k)
k = n - k;
// **** generate value of [n*(n-1)*---*(n-k+1)] / [k*(k-1)*---*1] ****
for (int i = 0; i < k; i++) {
res *= (n - i);
res /= (i + 1);
}
// **** return binomial coefficient ****
return res;
}
This function generates the binomial coefficient and returns it to the caller.
Please take a look at the comments section of the `catalan` function to verify the increase in performance. I also modified the name and submitted as the function of interest.
/**
* Given an integer n, return the number of structurally unique BST's (binary search trees)
* which has exactly n nodes of unique values from 1 to n.
*
* Runtime: 0 ms, faster than 100.00% of Java online submissions.
* Memory Usage: 35.3 MB, less than 93.57% of Java online submissions.
*/
static int numTrees(int n) {
// **** sanity check(s) ****
if (n <= 1) return 1;
// **** initialization ****
int arr[] = new int[n + 1];
arr[0] = arr[1] = 1;
// **** populate array ****
for (int i = 2; i <= n; i++) {
for (int j = 0; j < i; j++) {
arr[i] += arr[j] * arr[i - j - 1];
}
}
// ???? ????
// System.out.println("numTrees <<< arr: " + Arrays.toString(arr));
// **** return result ****
return arr[n];
}
Finally, after additional research I found a different way to compute the binomial coefficient. Once again, I submitted this implementation and got a very slight improvement from the previous pass.
Once again, most of the times in an interview, one is not allowed to consult the web or books. That said; engineers always consult both sources. The key is to read and understand what is being done editing the code.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Regards;
John