Most written technical tests have at least one question that goes - "How many Binary Search Trees can you form with n distinct numbers?" or "Number of internal nodes in an m-ary/k-ary tree?"

And I know for a fact, most of us draw small trees in the corner of our sheets. That

1. wastes precious time.

2. leaves out important cases.

So here's a list that is definitely not exhaustive, it'll be great if you could figure them out as you go along, helps remember. I'll keep adding more formulae as I come across them. But for now, this should do:

1. To answer the first question above,

No of BSTs using n numbers is

For those of you who haven't seen this before, this gives the Catalan sequence, and the number of binary search trees can be found using the Catalan Sequence too, if you know it. For instance, if n=3, C(3) = 5 which is the number of BSTs you can form from three nodes.

2. The number of Binary Trees that can be formed, however, is given by the n

No of Binary trees from n numbers is n! *

Here's a small example for the two formulae given above with n = 3 (say the nodes are 1, 2 and 3):

3! * 5 = 30

And I know for a fact, most of us draw small trees in the corner of our sheets. That

1. wastes precious time.

2. leaves out important cases.

So here's a list that is definitely not exhaustive, it'll be great if you could figure them out as you go along, helps remember. I'll keep adding more formulae as I come across them. But for now, this should do:

1. To answer the first question above,

No of BSTs using n numbers is

^{2n}C_{n }/ (n+1) (i)For those of you who haven't seen this before, this gives the Catalan sequence, and the number of binary search trees can be found using the Catalan Sequence too, if you know it. For instance, if n=3, C(3) = 5 which is the number of BSTs you can form from three nodes.

2. The number of Binary Trees that can be formed, however, is given by the n

^{th }catalan number * n! The formula given above (i) calculates the n^{th }catalan number.No of Binary trees from n numbers is n! *

^{2n}C_{n }/ (n+1)Here's a small example for the two formulae given above with n = 3 (say the nodes are 1, 2 and 3):

__Binary Search Trees__

^{6}C

_{3 }/ 4 = 5

```
1 1 2 3 3
\ \ / \ / /
2 3 1 3 1 2
\ / \ /
3 2 2 1
```

__Binary Trees__

3! * 5 = 30

```
1 1 2 2 3 3
/ \ / \ / \ / \ / \ / \
2 3 3 2 1 3 3 1 1 2 2 1
1 1 1 1 1 1 1 1
/ / / / \ \ \ \
2 3 2 3 2 3 2 3
/ / \ \ / / \ \
3 2 3 2 3 2 3 2
2 2 2 2 2 2 2 2
/ / / / \ \ \ \
1 3 1 3 1 3 1 3
/ / \ \ / / \ \
3 1 3 1 3 1 3 1
3 3 3 3 3 3 3 3
/ / / / \ \ \ \
2 1 2 1 2 1 2 1
/ / \ \ / / \ \
1 2 1 2 1 2 1 2
```

## No comments:

## Post a Comment