Generating all possible topologies in a full binary tree having n nodes

Question

I want to create all possible topologies of a full binary tree which must have exactly n+1 leaf nodes and n 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.

example: with 4 leaf nodes and 3 internal nodes.

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

PS: There is a simlar thread .It will be helpful If anybody can elaborate the tree generation algorithm suggested by coproc in this thread.

Thanks in advance.

Answer 1

I am using recursion here. This code can be improved by using dynamic programming. I hope this helps. We start by one node in the left, one node as root and N-i-1 nodes in the right. Then, we move nodes from the right to left as pairs.

import java.util.ArrayList;
import java.util.List;

public class NumberOfFullBTrees {

    public static void main(String[] args) {
        int N = 5;
        NumberOfFullBTrees numberOfFullBTrees = new NumberOfFullBTrees();
        List<TreeNode> result = numberOfFullBTrees.allPossibleFBT(N);
    }

    /**
     * Builds all possible full binary trees. We start by 1 node in left, 1 note at root and n-2 node in right.
     * We move the nodes in pairs from right to left. This method uses recursion. This method can be improved by
     * using dynamic programming.
     *
     * @param N The number of nodes
     * @return The possible full binary trees with N nodes as a list
     */
    public List<TreeNode> allPossibleFBT(int N) {
        List<TreeNode> result = new ArrayList<>();
        if (N % 2 == 0) {
            return result;
        }
        if (N == 1) {
            result.add(new TreeNode(0));
            return result;
        }
        for (int i = 1; i < N; i += 2) {
            List<TreeNode> lefts = allPossibleFBT(i);
            List<TreeNode> rights = allPossibleFBT(N - i - 1);
            for (TreeNode l : lefts) {
                for (TreeNode r : rights) {
                    TreeNode root = new TreeNode(0);
                    root.left = l;
                    root.right = r;
                    result.add(root);
                }
            }
        }
        return result;
    }

}

Answer 2

Here is the code for generating all possibles topologies for given n. Total Number of nodes (internal + leaf nodes) in a full binary tree is odd.

If a tree is full binary tree, then it's left and right sub trees are also full binary trees i.e both left and right sub trees have odd number of nodes.

For a given n, We generate all combinations of full binary tree like this

First Iteration: 1 Node on left hand side, 1 root, n-2 on right hand side.
Second Iteration: 3 Nodes on left hand side, 1 root, n-4 on right hand side.
Third Iteration: 5 Nodes on left hand side, 1 root, n-6 on right hand side. .
.
.
Last Iteration: n-2 Nodes on left hand side, 1 root, 1 on right hand side

In each iteration, we find all possible left trees and right trees. If L full trees are possible on left hand side, R full trees are possible on right hand side - then total number of trees is L*R

public void createAllTopologies(int n){

    if(n%2 == 0) return;

    Map<Integer, List<Node>> topologies = new HashMap<Integer, List<Node>>();

    topologies.put(1, new ArrayList<Node>());
    topologies.get(1).add(new Node(1));

    for(int i=3;i<=n;i+=2){

        List<Node> list = new ArrayList<Node>();

        for(int j=1;j<i;j+=2){
            List<Node> left = topologies.get(j);
            List<Node> right = topologies.get(i-j-1);
            list.addAll(generateAllCombinations(left,right));
        }
        topologies.put(i, list);
    }

    List<Node> result = topologies.get(n);

    for(int i=0;i<result.size();i++){
        printTree(result.get(i),0);
        System.out.println("-----------------------------");
    }

}

private List<Node> generateAllCombinations(List<Node> left, List<Node> right) {

    List<Node> list = new ArrayList<Node>();
    for(int i=0;i<left.size();i++){
        for(int j=0;j<right.size();j++){
            Node nNode = new Node(1);
            nNode.left = left.get(i).clone();
            nNode.right = right.get(j).clone();
            list.add(nNode);
        }
    }
    return list;
}

/* This prints tree from left to right fashion i.e 
       root at left, 
       leftNode at bottom, 
       rightNode at top 
*/

protected void printTree(Node nNode,int pos){
        if (nNode==null) {
            for(int i=0;i<pos;i++) System.out.print("\t");
            System.out.println("*");
            return;
        }
        printTree(nNode.right,pos+1);
        for(int i=0;i<pos;i++) System.out.print("\t");
        System.out.println(nNode.data);
        printTree(nNode.left,pos+1);

}

Please refer to complete code here - http://ideone.com/Wz2Jhm