# Unique Binary Search Trees | LeetCode | DP Solution, Explained

LeetCode 96. Unique Binary Search Trees. I explain the Dynamic Programming Solution in detail, along with intuitions on how to actually think about this problem. Problem Link.

## 0. Unique Binary Search Trees: Problem Discussion

### 0.0. I/O format

• Input: n
• Return: The number of unique BSTs

### 0.1. What are BSTs?

• The existence of nodes `x` and `z` is not necessary, but if they do (any of them), they should follow the condition `x < y < z`

## 1. Unique Binary Search Trees: Observations & Logic

### 1.0. Intuitions

In these type of counting problems, I like to aim for finding a pattern between the first few cases – maybe the `i+1`th answer is double of `i`th answer, or maybe there is a common difference between adjacent answers.

Its a good idea to look at the couple of smaller cases first, since they are easy to do manually, and in dp questions, they become a bliss. Let’s see what happens!

### 1.1. Observations

Huh. Maybe for n=x –> x? Let’s see a couple more examples to confirm or deny this.

Ah. For n = x –> x will not work. There’s something more going on. Look at the root of the trees for n = 3. Unique Binary Search Trees: n=3, marked all the roots of the trees

Interestingly enough, it looks as if there are some repeating sub-structures in the case of n = 3. Look at node `3` as an example. The nodes 1 and 2 will both be on the left side, and both have 2 arrangements they can be in – since n = 2 –> 2!

This means we are looking at a DP question.

In this case, we group the elements that would have come to the right and left side (using the property of BST), and we will call the appropriate n = 2 –> 2 OR n = 3 –> 5.

## 2. Unique Binary Search Trees: Implementation

The implementation is straightforward once we understand the DP logic:

• calculate some base cases, dp = dp = 1
• where dp[i] represents the answer for the `i`th node, as in, n = i –> dp[i]
• then, for each `i`, we try to find all the possible arrangements, each time increasing the left_side count by 1, and decreasing the right_side count by 1 simultaneously.

### 2.0. Code

```class Solution:
def numTrees(self, n: int) -> int:
dp = *(n+1)
dp = 1
dp = 1

for i in range(2, n+1):
dp[i] = 0

l, r = 0, i-1
while l < i:
dp[i] += dp[l]*dp[r]
l += 1
r -= 1

return dp[n]```

### 2.1. Complexity Analysis

• Time: O(N2). O(N) to iterate over all the Ns and another O(N) nested to consider all left and right combinations.
• Space: O(N). To store all the dp values.

##### Tanishq Chaudhary Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.

### Recommended Posts

##### Gas Station | InterviewBit | Solution Explained

June 13, 2022

##### Reverse integer | InterviewBit | LeetCode | Solution Explained

January 24, 2022

##### Furthest Building You Can Reach | LeetCode | Solution Explained

January 20, 2022

This site uses Akismet to reduce spam. Learn how your comment data is processed.