CODEWITHSUNDEEP
algorithmdata-structurestreebinary-treebinary-search-tree
Ashok Bijoy Debnath
Ashok Bijoy Debnath

Reputation: 1503

Number of binary trees and BSTs with node n

If number of nodes = n, we have

  1. No. of BSTs = C(n)
  2. No. of structurally different binary trees = C(n)
  3. No. of binary trees = n! * C(n)

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

Answers (3)

justmscs
justmscs

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

amit
amit

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

Hesham Attia
Hesham Attia

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

Related Questions