1.
Understanding
2.
Problem Statement
2.1.
Examples
3.
Approach 1
3.1.
Algorithm
3.2.
Program
4.
Approach 2
4.1.
Algorithm
4.2.
Program
4.3.
Complexity Analysis
5.
5.1.
What is the level order traversal of a tree?
5.2.
Why do we use a queue in a level order traversal of a tree?
6.
Conclusion
Last Updated: Mar 27, 2024

Print all possible N-nodes Full Binary Trees

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Understanding

In this blog, we will discuss a problem based on binary trees. Binary trees are a widely asked topic in coding contests and technical interviews. There are different types of binary trees: complete binary tree, perfect binary tree, degenerate binary tree, full binary tree, etc. This blog will take up a challenge based on Full Binary Trees. We will learn to break the problem into smaller subproblems and solve each part using dynamic programming with memoization.

Also see, Data Structures

Problem Statement

Ninja has given you an integer N. Your task is to print all possible distinct Full binary trees with the number of nodes equal to N.

Two full binary trees are different if and only if they are structurally different, i.e., the values in the nodes do not contribute to be a criterion for different full binary trees.

Full Binary Tree

A binary tree is said to be a full binary tree if every node in the tree has either 0 or 2 children.

Examples

Full Binary Trees

Output Format

Output each binary tree in the prescribed format:

Print the value of the root. For each node in the binary tree, starting with the root, print the value of its left and right child (null if empty). If they are not null, repeat the same process for its left and right child(in the same order).

Input

N = 5

Output

value value value null null value value null null null null

value value value value value null null null null null null

Explanation

Possible full binary trees with five nodes:

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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 ROOTwith 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_CHILDLEFT 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 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;
}``````

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 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;
}``````

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

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.