# Unique Binary Search Trees ## Problem Statement Given *n*, how many structurally unique **BST's** (binary search trees) that store values `1... n`? ## Testcase ``` Example 1: Input: 3 Output: 5 Explanation: Given n = 3, there are a total of 5 unique BST's: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3 ``` ## Prerequisite Knowledge ### Dynamic Programming Refer to the *Prerequisite Knowledge* section in **Coin Change 2**: {% content-ref url="../week-1/coin-change-2" %} [coin-change-2](https://keerthisreeraghu.gitbook.io/june-leetcoding-challenge/week-1/coin-change-2) {% endcontent-ref %} ### Catalan Number A sequence of non-negative numbers which commonly appears in combinatorial problems is known as Catalan Numbers. It often involves recursively defined objects. **Euler's Polygon Division Problem** asks the question, *"In how many ways can a regular `n-gon` be divided into `n-2` triangles if different orientations are counted separately?"* In tree enumeration problems such as the one given above, the solution involves the Catalan Sequence. ![Source: https://mathworld.wolfram.com/CatalanNumber.html](https://3540593164-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M9DtKfC4RdOdz3G4SbS%2F-MAdWhl7oW6jMfrR0OG6%2F-MAdi6neGzX6TgvZLnAV%2Fimage.png?alt=media\&token=221bb002-9533-4727-9014-3379ca7eceff) #### Formula The nth Catalan Number is given by: ``` C(n) = (2n)! / ((n + 1)! * n!) ``` #### Catalan Series The first few Catalan Numbers starting from 0 are:`1, 1, 2, 5, 14, 42, 132, 429, 1430,...` ## Problem Explanation In this problem, we must find the number of unique binary search trees that can be formed using a given number of nodes. In order to calculate the number of arrangements of nodes, we must choose the number of nodes in the left sub-tree and the number of nodes in the right sub-tree while considering each node as the root node. #### Example Consider `n = 5`. We can derive the following combinations: 1. `root = 1`->`left nodes = 0` | `right nodes = 4`->`f[0]*f[4]` 2. `root = 2`->`left nodes = 1` | `right nodes = 3`->`f[1]*f[3]` 3. `root = 3`->`left nodes = 2` | `right nodes = 2`->`f[2]*f[2]` 4. `root = 4`->`left nodes = 3` | `right nodes = 1`->`f[3]*f[1]` 5. `root = 5`->`left nodes = 4` | `right nodes = 0`->`f[4]*f[0]` Therefore, for `n = 5` nodes, the total number of binary search trees can be represented as:\ `f[5] = f[0]*f[4] + f[1]*f[3] + f[2]*f[2] + f[3]*f[1] + f[4]*f[0]` #### Generalized Formula `f[n] = f[0]*f[n-1] + f[1]*f[n-2] + ... + f[n-2]*f[1] + f[n-1]*f[0]` ## Algorithm ### Bottom-Up DP Approach The intuitive approach would be to use a bottom-up dynamic programming approach to construct unique binary search trees by using each node of the tree as a root node to derive different combinations. The recursive formula to find the total number of combinations is: ``` G(n) = G(0) * G(n-1) + G(1) * G(n-2) + … + G(n-1) * G(0) ``` 1. Create a vector to store the solutions of each sub-problem. 2. Initialize `dp[0]` as 1 to account for the first solution with the root being set as 1. 3. For each node in the tree, compute the number of unique binary search trees that can be formed using this node as the root node, by applying the formula: `dp[i] += dp[j-1] * dp[i-j]`. {% hint style="info" %} Time Complexity: O(m\*n) {% endhint %} ### Mathematical Approach In this approach, we use the Nth Catalan Number formula to find the number of ways in which the nodes can be arranged to form unique binary search trees. ``` C(n) = (2n)! / ((n + 1)! * n!) ``` The reason for this can be attributed to the pattern that can be observed when we examine the number of nodes and the number of possible combinations that could be formed. 1. `n = 1`->`c = 1` 2. `n = 2`->`c = 2` 3. `n = 3`->`c = 5` 4. `n = 4`->`c = 14` 5. `n = 5`->`c = 42` From the values of `c` that we have obtained, we can observe that the pattern is similar to that of the Catalan Numbers series as illustrated in the *Prerequisite Knowledge* section. {% hint style="info" %} Time Complexity: O(n) {% endhint %} ## Code {% code title="Dynamic Programming Approach" %} ```cpp int numTrees(int n) { vector dp(n + 1, 0); // When 1 is set as root, // left subtree = 0 children, right subtree = dp[n - 1] children // Set dp[0] = 1 dp[0] = 1; for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) { // If k is set as the root node, // left subtree = (k - 1) children // right subtree = (n - k) children dp[i] += dp[j - 1] * dp[i - j]; } } return dp[n]; } ``` {% endcode %} {% code title="Mathematical Approach" %} ```cpp int numTrees(int n) { long long count = 1; for(int i = n + 1; i <= 2 * n; i++) { count = count * i / (i - n); } return count / (n + 1); } ``` {% endcode %} --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://keerthisreeraghu.gitbook.io/june-leetcoding-challenge/week-4/unique-binary-search-trees.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.