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:
 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.
 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

If N is even, return an empty array as the number of nodes in a full binary tree is always odd.

Create a recursive function allPossibleFullBT with the parameter N and put the following pseudocode inside it:
 Create a list L that will contain all full binary trees with N number of nodes.
 If N = 1, then L = [[0, null, null]].

Iterate from 0 to N1 using variable X and execute the following pseudocode in each iteration:
 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.
 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.
 Append root in L.
 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;
}
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 recalculating it the next time, we can use the stored value. This is a wellknown 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
 If N is even, return an empty array as the number of nodes in a full binary tree is always odd.
 Initialize a hash, say fullBT, that maps an integer N to a list of all full binary trees with N number of nodes.

Create a recursive function allPossibleFullBT with the parameter N and put the following pseudocode inside it:
 Create a list L that will contain all full binary trees with N number of nodes.
 If N = 1, then L = [[0, null, null]].

Iterate from 0 to N1 using variable X and execute the following pseudocode in each iteration:
 Generate all full binary trees of size X and NX1 by recursively calling allPossibleFullBFT with these parameters. Let them be left_trees and right_trees, respectively.
 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.
 Append root in L.
 Set fullBT[N] = L.
 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;
}
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 breadthfirst traversal of a tree in which we traverse the tree levelwise. 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:
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:
Cheers!