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 2nCn / (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 nth catalan number * n! The formula given above (i) calculates the nth catalan number.
No of Binary trees from n numbers is n! * 2nCn / (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
Binary Trees
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 2nCn / (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 nth catalan number * n! The formula given above (i) calculates the nth catalan number.
No of Binary trees from n numbers is n! * 2nCn / (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
6C3 / 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
