Reputation: 1503
If number of nodes = n, we have
where C(n) = Catalan number = (2n)! / [ (n+1)! * n! ]
I understand #1. I can do it using BST property [ Code below ]. Can anyone please tell me how to arrive at #2 and #3 ? Thanks.
public static long countBST_dp(int n) {
if(n == 0 || n == 1) return 1;
long[] arr = new long[n+1];
arr[0] = 1; arr[1] = 1;
for (int i = 2; i < arr.length; i++) {
int isum = 0;
for (int k = 1; k <= i; k++) {
isum += arr[k-1] * arr[i-k];
}
arr[i] = isum;
}
return arr[n];
}
Upvotes: 1
Views: 853
Reputation: 756
2. No. of structurally different binary trees = C(n)
From Wikipedia, Catalan number satisfy the recurrence relation:
C(0) = 1, C(1) = 1
C(n) = C(0)*C(n-1) + C(1)*C(n-2) + ... + C(n-1)*C(0)
Denote h(n) = No. of structurally different binary trees with node n
,then:
h(0) = 1
h(1) = 1
...
With n node, left subtree of root may have 0,1,...,n-1 nodes
accordingly right subtree have n-1,n-2,...,0 nodes, so:
h(n) = h(0)*h(n-1) + h(1)*h(n-2) + ... + h(n-1)*h(0) = C(n)
3. No. of binary trees = n! * C(n)
If structure of a binary tree is fixed, we can "fill in" the tree with n
distinct values in n!
ways.
There are C(n)
structures, so No. of binary trees = n! * C(n)
.
Upvotes: 0
Reputation: 178521
No. of structurally different binary trees - in here the order does not matter, all vertices are the same - all that matters is the structure. So, we can make a bijection - given a BST, create a tree where all nodes are identical. Now, given two different BSTs - you are going to get two different trees that nodes are identical (otherwise there was a difference between the two in the order of nodes, and thus the tree is not BST) - so our function is injective. Also, there is some BST that can "generate" any 'structural tree' - so our function is sujective.
Since we found a bijection from {T | T is a BST of nodes [1,2,...,n]}
to {T | T is a binary tree where all nodes are identical}
- the size of the two sets is the same. Since we know the first set if of size C(n)
- the second one also is.
No. of binary trees = n! * C(n)
For every tree T
from {T | T is a binary tree where all nodes are identical}
, we can generate n!
different trees such that the nodes differ from each other by applying all permutations on the nodes. Thus, there are |{T | T is a binary tree where all nodes are identical}| * n!
different trees such that the nodes are different from each other. Since we have already proved the size of the set is the catalan number, we get C(n)*n!
Upvotes: 3
Reputation: 977
For #1, you can watch this: Count Number of Binary Search Tress given N Distinct Elements
For #2, you can watch this: Number of Binary Trees with n nodes
The basic idea is that we take a node as the root and distribute the rest on the left and right subtrees, which are a smaller subproblems of the original one.
For #3, it's the number of different binary trees (#2) multiplied by the different number arrangements for every tree (n!). Think about it as filling the BST with any permutation of the n numbers.
Upvotes: 0