Oh I see. I think I might have been mistaken in my words. I was not trying to generate all possible binary tree given of N nodes size. What I was trying to do was given a general tree, make all possible binary combination of that general tree,. Which is why I posted the above modification on your algorithm. I think its the same process as your algorithm. Unless, I'm being confused somewhere.
I am the confused one. I still don't understand what problem you are trying to solve, so I solved one that sounds similar but I understand.
If you post a detailed description of what you are trying to do, I'll try to help you.
EDIT: and sorry, I was referring more to the reoccurrence relation.[/quote]
You pick a tree of depth n-1 to put on the left and a tree of depth n-1 to put on the right, or you leave the left empty and put a tree of depth n-1 on the right, or you leave the right empty and put a tree of depth n-1 on the left. The total count is:
[quote name='D.Chhetri' timestamp='1297906569' post='4775221']
Oh I see. I think I might have been mistaken in my words. I was not trying to generate all possible binary tree given of N nodes size. What I was trying to do was given a general tree, make all possible binary combination of that general tree,. Which is why I posted the above modification on your algorithm. I think its the same process as your algorithm. Unless, I'm being confused somewhere.
I am the confused one. I still don't understand what problem you are trying to solve, so I solved one that sounds similar but I understand.
If you post a detailed description of what you are trying to do, I'll try to help you.
EDIT: and sorry, I was referring more to the reoccurrence relation.[/quote]
You pick a tree of depth n-1 to put on the left and a tree of depth n-1 to put on the right, or you leave the left empty and put a tree of depth n-1 on the right, or you leave the right empty and put a tree of depth n-1 on the left. The total count is:
I can't try to explain the problem in complete detail, because its too much. But the problem at hand right now is this: I have a general tree, for example :
ROOT
/ | \
c1 c2 c3
Now I need to take the above tree, and generate all possible binary tree from it. For example , an instance could be :
ROOT
/ \
p1 c3
/ \
c1 c2
So essentially, p1 is a 'combined' child. Another instance could be :
ROOT
/ \
c1 p3
/ \
c2 c3
and so on. I need to create all possible binary tree's from the given general trees. At first I thought there was Combination(numberOfNodes,2) of different combination, then I realized that those combinations
could it self be turned into trees. So I think there could possible be C(n,2)*C(n-2 , 2) ... C(2,2) number of combinations. But as shown its 2^( 2^(n-1) ) + 1
The problem I solved is roughly equivalent to transforming a tree of depth 1 (like the one you just used as an example) into a binary tree in all possible ways. If you have a more complicated tree, you can still use this algorithm at any level where you find more than two branches.
You can use some form of backtracking to solve your original problem: You traverse the original tree in some order, and when you find a node with more than two descendants, you try cutting the descendants in two non-empty groups in every way possible. Since the order seems to matter, you'll have k-1 possible cuts if there are k descendants.
I can see how writing this recursive algorithm can be tricky. Good luck.
Several of your posts state or hint that you want to actually create them all, simultaneously.
Are you including all forms of binary trees, not just those that are balanced? If so, the existing combinatorial explosion gets much, much, much worse than the above posts say.
If you limit yourself to balanced binary trees you will have bigger than factorial growth for most numbers. A full balanced tree will be exactly factorial, and incomplete balanced trees will be more than factorial because the incomplete nodes can shuffle among the bottom row. For 15 items in a fully balanced tree that's 1.3*10^12 permutations.
If you want to have all possible layouts, not just balanced binary trees, you are going to have a tremendous number of variations. Just trying to come up with a formula to express it makes my brain work up a sweat, but the number has extremely rapid growth. The growth for all possible tree layouts makes the factorial growth of balanced trees look easy.
Is it enough to simply iterate over them, or do you need to actually create every one of them? Consider that with just 10 nodes and allowing unbalanced trees you will have more variations than you can access with 32-bit memory pointers. If you need to actually process them all I cannot imagine how a brute force method will work for any non-trivial number of nodes.
