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.

Edited by pdwivedi

3 Years
Discussion Span
Last Post by pdwivedi

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.

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.

Edited by pdwivedi: Corrected the formatting

This article has been dead for over six months. Start a new discussion instead.
Please be thoughtful and detailed and be sure to adhere to our posting rules.