Binary tree problem

[pdwivedi]

Hi all,

I want to create all possible combinations of a full binary tree which must have exactly 4 leaf nodes and 3 internal nodes.

I want to create it using recursion and tree must be simple binary tree not a binary search tree or BST.

Kindly suggest algorithm to achieve this task.

Thanks in advance.

[pdwivedi]

edite
d.

[mike_2000_17]

Any standard permutation algorithm will do. You have seven slots to fill, and you can permute the elements just like you would permute the elements of any array. C++ has a standard implementation for it.

[mike_2000_17]

Just to add to that, a full binary tree is usually stored in an array as follows:

[Root] [Child-1] [Child-2] [Leaf-1] [Leaf-2] [Leaf-3] [Leaf-4]

That's called a breadth-first layout. In other words, it is just an array of 7 elements, and you interpret the first element as being the root and so on for subsequent elements. If you permute the elements around that array 7! times you get all the possible binary trees.

[pdwivedi]

Thanks guys for your response.But I think you misunderstood the question.I point out some clarifications

1. I do not want combination of nodes instead it should be  all possible toplogies of tree for example .

     N                  N                  N
    / \                / \                 /\
   N   N               N  N               N  N
  /\   /\             /\                     /\
 N  N  N N           N  N                    N N
                    / \                        /\
                    N  N                       N N

2. If possible it should be constructed using  recursion.