perfect hash for binary tree. Catalan Number.

binary.c

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
        
int fact(int n){
    int r, i;
    r = 1;      
    for(i=1;i<=n;i++){
        r *=i;
    }   
    return r;
}       
        
int catalan(int n){
    return fact(2*n)/(fact(n+1)*fact(n));
}       
        
    
    

int btree(int n, int hash, char* buf){
    int count;
    int i, j, k;
    int sum, chunk;
    
    printf("%d, %d, %s\n",n, hash, buf);

    if(n == 0){
        *buf = 'l';
        printf("leaf\n");
        return 1;
    }else{
        sum = 0;
        for(i=0;i<n;i++){
            chunk = catalan(i)*catalan(n-1-i);
            if ((sum<=hash) &&(hash < sum+chunk)){
                break;
            }
            sum += chunk;
        }
        hash -= sum;
        j = catalan(i);
        count = btree(i, hash%j, buf);
        count += btree(n-1-i, hash/j, buf+count);
        printf("node %d\n", i);
        *(buf+count) = 'n';
        count+=1;
    }
    return count;
}



int main(){
    char* buf;
    int c, i;


    c = catalan(4);
    buf = malloc(2*c+2);
    buf[2*c+1] = '\0';
    //btree(3, 0, buf);
    //printf("%s\n", buf);
    for(i=0;i<c;i++){
        btree(4, i, buf);
        printf("%s\n", buf);
    }
    return 0;
}