Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Problem of the day

You have been given a number ‘NUM’. Your task is to count total structurally unique binary search trees from keys 1 to ‘NUM’ considering we should use each key from 1 to ‘NUM’ only once.

Two binary search trees are different if there is at least one node during traversal which is different in values or present in one tree but not present in another tree.

```
The answer can be large, hence the return answer % ‘MOD’, where ‘MOD’ is a large prime number (10^9 + 7).
```

Detailed explanation

```
1 <= T <= 100
1 <= NUM <= 500
Time limit: 1 sec
```

```
2
2
1
```

```
2
1
```

```
In the first test case, 2 unique BST are possible.
```

```
In the second test case, only 1 tree is possible.
```

```
2
3
4
```

```
5
14
```

```
In the first test case, 5 unique BST are possible.
```

```
In the second test case, similar to the above way, 14 unique BST are possible.
```