Print all possible N-nodes Full Binary Trees

Approach 1

As you can observe, we can break down the problem into smaller subproblems. For a full binary tree with N number of nodes, we can do the following:

1. Create all full binary trees LEFT_TREES with X number of nodes and all full binary trees right_trees with N - X - 1 nodes where X varies from 0 to N - 1.
2. Create a new node, say ROOT, with its children null initially. Now for each binary tree LEFT in LEFT_TREES and each binary tree RIGHT in RIGHT_TREES, create a new binary tree of N nodes with ROOT.LEFT_CHILD = LEFT and ROOT.RIGHT_CHILD=RIGHT.

We can create all full binary trees of size N using full binary trees of sizes less than N.

As you can see, we can recursively call the function that generates all full binary trees of size N to generate all full binary trees of size X and N - X - 1.

Now can you guess which algorithmic technique we generally use to solve a problem that can be broken down into smaller subproblems?

Yeah, you guessed it right—recursion.

Algorithm

1. If N is even, return an empty array as the number of nodes in a full binary tree is always odd.
2. Create a recursive function allPossibleFullBT with the parameter N and put the following pseudocode inside it:
   1. Create a list L that will contain all full binary trees with N number of nodes.
   2. If N = 1, then L = [[0, null, null]].
   3. Iterate from 0 to N-1 using variable X and execute the following pseudocode in each iteration:
      1. Generate all full binary trees of size X and N - X - 1 by recursively calling allPossibleFullBFT with these parameters. Let them be left_trees and right_trees, respectively.
      2. For each tree left in left_trees and right in right_trees, create a new node, say root, and set root.left = left and root.right = right.
      3. Append root in L.
3. Print the binary trees of size N returned by the recursive function.

Program

#include <iostream>
#include <vector>
using namespace std;
 
// Binary tree node.
class Node
{
public:
    int val;
    Node *left, *right;
 
    Node(int val)
    {
        this->val = val;
        this->right = this->right = NULL;
    }
};
 
// Utility function to display a tree as an array.
void displayTree(Node *node)
{
    if (node == NULL)
        return;
 
    if (node->left == NULL)
        cout << "null ";
    else
        cout << "value ";
 
    if (node->right == NULL)
        cout << "null ";
    else
        cout << "value ";
 
    displayTree(node->left);
    displayTree(node->right);
}


// Recursive function to generate all full binary trees having nodes 'N'.
vector<Node *> allPossibleFullBT(int N)
{
    vector<Node *> finalAns;
    if (N == 1)
    {
        // Only possible full binary tree.
        Node* newNode = new Node(0);
        finalAns.push_back(newNode);
    }
    // Number of nodes in a full binary tree is always odd.
    else if (N % 2 == 1)
    {
        for (int i = 0; i < N; i++)
        {
            // Create all possible full binary trees of size 'i'.
            vector<Node *> leftTrees = allPossibleFullBT(i);
 
            // Create all possible full binary trees of size 'n - 1 - i'.
            vector<Node *> rightTrees = allPossibleFullBT(N - 1 - i);
 
            for (Node *left : leftTrees)
            {
                for (Node *right : rightTrees)
                {
                    // Creating root node.
                    Node *root = new Node(0);
 
                    // Attaching left subpart.
                    root->left = left;
 
                    // Attaching right subpart.
                    root->right = right;
 
                    // Adding 'ROOT' in the 'FINAL_ANS'.
                    finalAns.push_back(root);
                }
            }
        }
    }


    return finalAns;
}
 
int main()
{
    int n;
    cin >> n;
    vector<Node *> allFullBTs = allPossibleFullBT(n);
    for (Node *tree : allFullBTs)
    {
        // For the root.
        cout << "value ";
       
        displayTree(tree);
        cout << endl;
    }
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input

5

Output

value value value null null value value null null null null

value value value value value null null null null null null

Approach 2

Can we do any better? As you can observe in the algorithm mentioned in approach 1, we are making multiple calls to find all full binary trees of a particular size. If we store full binary trees of a particular size, then instead of re-calculating it the next time, we can use the stored value. This is a well-known programming technique. Can you guess the name?

Yeah, you guessed it right—dynamic Programming with memoization. We can maintain a hash that maps an integer N to a list of all full binary trees with N number of nodes.

Algorithm

1. If N is even, return an empty array as the number of nodes in a full binary tree is always odd.
2. Initialize a hash, say fullBT, that maps an integer N to a list of all full binary trees with N number of nodes.
3. Create a recursive function allPossibleFullBT with the parameter N and put the following pseudocode inside it:
   1. Create a list L that will contain all full binary trees with N number of nodes.
   2. If N = 1, then L = [[0, null, null]].
   3. Iterate from 0 to N-1 using variable X and execute the following pseudocode in each iteration:
      1. Generate all full binary trees of size X and N-X-1 by recursively calling allPossibleFullBFT with these parameters. Let them be left_trees and right_trees, respectively.
      2. For each tree left in left_trees and right in right_trees, create a new node, say root, and set root.left = left and root.right = right.
      3. Append root in L.
   4. Set fullBT[N] = L.
4. Print the binary trees of size N from fullBT.

Program

#include <iostream>
#include <vector>
#include <map>
using namespace std;
 
// Binary tree node.
class Node
{
public:
    int val;
    Node *left, *right;
 
    Node(int val)
    {
        this->val = val;
        this->right = this->right = NULL;
    }
};
 
// Utility function to display a tree as an array.
void displayTree(Node *node)
{
    if (node == NULL)
        return;
 
    if (node->left == NULL)
        cout << "null ";
    else
        cout << "value ";
 
    if (node->right == NULL)
        cout << "null ";
    else
        cout << "value ";
 
    displayTree(node->left);
    displayTree(node->right);
}
 
// For hashing.
map<int,vector<Node*>> fullBT;


// Recursive function to generate all full binary trees having nodes 'N'.
vector<Node *> allPossibleFullBT(int N)
{
    // Memoization check.
    if(fullBT.find(N) != fullBT.end()){
        return fullBT[N];
    }
    vector<Node *> finalAns;
    if (N == 1)
    {
        // Only possible full binary tree.
        Node* newNode = new Node(0);
        finalAns.push_back(newNode);
    }
    // Number of nodes in a full binary tree is always odd.
    else if (N % 2 == 1)
    {
        for (int i = 0; i < N; i++)
        {
            // Create all possible full binary trees of size 'i'.
            vector<Node *> leftTrees = allPossibleFullBT(i);
 
            // Create all possible full binary trees of size 'n - 1 - i'.
            vector<Node *> rightTrees = allPossibleFullBT(N - 1 - i);
 
            for (Node *left : leftTrees)
            {
                for (Node *right : rightTrees)
                {
                    // Creating root node.
                    Node *root = new Node(0);
 
                    // Attaching left subpart.
                    root->left = left;
 
                    // Attaching right subpart.
                    root->right = right;
 
                    // Adding 'ROOT' in the 'FINAL_ANS'.
                    finalAns.push_back(root);
                }
            }
        }
    }
    
    fullBT[N] = finalAns;
    return finalAns;
}
 
int main()
{
    int n;
    cin >> n;
    vector<Node *> allFullBTs = allPossibleFullBT(n);
    for (Node *tree : allFullBTs)
    {
        // For the root.
        cout << "value ";
       
        displayTree(tree);
        cout << endl;
    }
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input

5

Output

value value value null null value value null null null null

value value value value value null null null null null null

Complexity Analysis

Time Complexity

The time complexity of the above approach is O(2^N).

Space Complexity

The space complexity of the above approach is also O(2^N).

Frequently Asked Questions

What is the level order traversal of a tree?

Level Order Traversal is a breadth-first traversal of a tree in which we traverse the tree level-wise. In this, we first cover all the nodes of a present level then move to the next level of the tree.

Why do we use a queue in a level order traversal of a tree?

In level order traversal, we need to traverse the nodes in the order in which they are stored, i.e., while traversing the current level of the tree, we store the children of these nodes, and we need to process those children nodes in an order in which they are stored. That's why we use a 'queue' data structure as it is a "First In First Out" type of data structure.

Conclusion

We learned to use dynamic programming with memoization in this blog to solve the problem. We also used simple recursion with no memoization to solve the problem. But the time complexity of this approach was much larger than what we have achieved. We used hashing to store the lists of full binary trees. Thus, this blog links many concepts to arrive at the solution.

Recommended Reading:

• Binary Tree vs Binary Search Tree
• Check Whether Every Node of the Binary Tree has a Value K on Itself or Any Immediate Neighbors
• Check if Binary Tree is an Even Odd Tree
• Check if a Given Binary Tree is a Sum Tree
• Print All Root To Leaf Paths With a Maximum Count of Even Nodes
• Print All Root To Leaf Paths With Their Relative Position
• Print Levels of All Nodes in a Binary Tree
• Print All Nodes That Are At Distance K From a Leaf Node
   

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Recommended Problems:

• Print Nodes At Distance K From Node
• Kth Ancestor Of A Node In Binary Tree
• Segregate Even And Odd Nodes In A Linked List
   

Cheers!