CODEWITHSUNDEEP
javaalgorithmtreebinary-treecatalan
aviad
aviad

Reputation: 8278

How to find number of possible binary tree topological permutations?

Given number of binary tree nodes (X) write method that returns the number of random permutations of binary trees with X nodes.

Examples:

X=1: 1

     o

X=2: 2

     o    o
   o        o

X=3: 5

        o    o          o     o        o
      o        o      o         o    o   o
    o            o      o     o

I ended up with :

    public static int numOfPerms(int numOfNodes) {
       if (numOfNodes<=2 && numOfNodes > 0) {
           return numOfNodes;
       }
       int res = 1;
       for (int i=1; i<=numOfNodes; i++) {
           res = res*(4*i-1)/(i+1);
       }
       return res;
    }

I would appreciate sharing here better solutions.

Upvotes: 3

Views: 2487

Answers (3)

Haile
Haile

Reputation: 3180

I think the Catalan Numbers can count your trees (See the part about applications in combinatorics). They form a well know sequence usually defined by this recurrence relations:

recurrence relation for C_n

This recurrence often arises in enumeration problems about tree or recursive structures, so it's quite well studied. The wikipedia entry I linked gives a number of useful closed-form expressions for the n-th Catalan number, i.e.

closed formulae

all of them are suitable for code implementation, and a lot faster than any recursive approach.

Upvotes: 5

Meisam
Meisam

Reputation: 435

Try this recursive method:

static int numOfPerms(int numOfNodes) {
    if (numOfNodes == 1) {
        return 1; 
    }

    numOfNodes = numOfNodes - 1;
    return ((numOfPerms(numOfNodes) * (2*numOfNodes+2) * 
            (2*numOfNodes+1))/((numOfNodes+1)*(numOfNodes+2)));
}

Upvotes: 2

brimborium
brimborium

Reputation: 9512

Ok, as far as I can see, your solution is not correct, right? (for numOfNodes=4 it returns 12 instead of 14)

Intuitively, I would go for a recursive approach.

  1. Use up one node as parent node
  2. for all possible divisions into two sets, recursively call the function for both sets
  3. multiply the results from the two sets of each division and sum up the products of all the divisions
  4. return the sum

But before implementing it, I would make sure that there is no simple formula for this. I did not find one on the quick (which does not mean that there isn't one).

EDIT: As already stated in another answer: You could also just calculate the n-th Catalan number.

Upvotes: 4

Related Questions