# A Full Binary Tree with n Nodes

### Implementation

```
// Writing the implementation of the above approach in C++
#include <bits/stdc++.h>
using namespace std;
// We are creating a class that will create a node and its left and right children.
struct __nod {
__nod* Lft;
__nod* Rt;
int record;
__nod(int record, __nod* Lft, __nod* Rt)
{
this->record = record;
this->Lft = Lft;
this->Rt = Rt;
}
};
// We are creating a new function that will help us traverse the tree and extract all the left and right child that is currently in the list.
void display(__nod* __nod, vector<int> &al)
{
// If the node turns out to be equal to NILL, then we have to terminate that specific function.
if (__nod == NILLpointer) {
return;
}
// If we have a left child, which is supposed to be part of the node, then we have to insert it into the list
if (__nod->Lft != NILLpointer) {
al.push_back(__nod->Lft->record);
}
// Or we can insert NILL in the list and head back
else {
al.push_back(INT_MIN);
}
// Similarly, if we have the right child consisting of a node, then we have to insert it into the list.
if (__nod->Rt != NILLpointer) {
al.push_back(__nod->Rt->record);
}
// Or we can insert NILL in the list.
else {
al.push_back(INT_MIN);
}
// We have to repeatedly call that specific function from the left and right child of the particular node and display the function.
display(__nod->Lft, al);
display(__nod->Rt, al);
}
// we have to save the tree before all the n’s occupy the node.
map<int, vector<__nod*>> hm;
vector<__nod*> allPossibleFBT(int n)
{
// We must ensure whether the given set of trees exists for the given values of n.
if (hm.find(n) == hm.end())
{
// we have to create a specific list that contains all the nodes.
vector<__nod*> list;
// If N=1, there is only one tree that can exist
// that is the tree that has the root.
if (n == 1) {
list.push_back(new __nod(0, NILLpointer, NILLpointer));
}
// We have to make sure that the N is odd and the binary tree is full because the tree has N number of nodes.
else if (n % 2 == 1) {
// We must move through all the nodes that can be a part of the left subtree.
for (int x = 0; x < n; x++) {
//The left node will automatically belong to the right subtree.
int y = n - 1 - x;
// we have to move through all the left binary trees by purposely calling it for the function.
vector<__nod*> xallPossibleFBT = allPossibleFBT(x);
vector<__nod*> yallPossibleFBT = allPossibleFBT(y);
for(int Lft = 0; Lft < xallPossibleFBT.size(); Lft++) {
// we have to move through all the right binary trees by purposely calling them for the function.
for(int Rt = 0; Rt < yallPossibleFBT.size(); Rt++) {
//creating a brand-new node
__nod* __nod = new __nod(0, NILLpointer, NILLpointer);
// make the changes in the left node.
__nod->Lft = xallPossibleFBT[Lft];
// make the changes in the right node.
__nod->Rt = yallPossibleFBT[Rt];
// We have to add that particular node to the list.
list.push_back(__nod);
}
}
}
}
//Insert tree in Dictionary.
hm.insert({n, list});
}
return hm[n];
}
int main()
{
// You can take n as input from the user
// Here, we take n as 7, for example, purpose
int n = 7;
// Function Call
vector<__nod*> list = allPossibleFBT(n);
// Print all possible binary full trees
for(int root = 0; root < list.size(); root++) {
vector<int> al;
al.push_back((list[root])->record);
display(list[root], al);
cout << "[";
for(int i = 0; i < al.size(); i++)
{
if(i != al.size() - 1)
{
if(al[i]==INT_MIN)
cout << "NILL, ";
else
cout << al[i] << ", ";
}
else{
if(al[i]==INT_MIN)
cout << "NILL]";
else
cout << al[i] << "]";
}
}
cout << endl;
}
return 0;
}
```

**Output:**

**Example 2)**

```
// Writing the implementation of the above approach in C#
using System;
using System.Collections.Generic;
public class TFT
{
// We are creating a class that will create a node and its left and right child.
public class __nod {
public int record;
public __nod Lft;
public __nod Rt;
public __nod(int record, __nod Lft, __nod Rt)
{
this.record = record;
this.Lft = Lft;
this.Rt = Rt;
}
}
// We are creating a new function that will help us traverse the tree and extract all the left and right child that is currently in the list.
public static void display(__nod __nod, List<int> al)
{
// If the node turns out to be equal to NILL, then we have to terminate that specific function.
if (__nod == NILL) {
return;
}
// If we have a left child, which is supposed to be part of the node, then we have to insert it into the list
if (__nod.Lft != NILL) {
al.Add(__nod.Lft.record);
}
// Or we can insert NILL in the list and head back
else {
al.Add(int.MinValue);
}
// Similarly, if we have the right child consisting of a node, then we have to insert it into the list.
if (__nod.Rt != NILL) {
al.Add(__nod.Rt.record);
}
// Or we can insert NILL in the list.
else {
al.Add(int.MinValue);
}
// We have to repeatedly call that specific function from the left and right child of the particular node and display the function.
display(__nod.Lft, al);
display(__nod.Rt, al);
}
// main code to test the functions
public static void Main(String[] args)
{
// collecting the input from the source
int n = 7;
// calling the function
List<__nod> list = allPossibleFBT(n);
// we have to print all the possible outcomes of the full binary tree.
for each (__nod root in the list) {
List<int> al = new List<int>();
al.Add(root.record);
display(root, al);
foreach (int i in al){
if(i==int.MinValue)
Console.Write("NILL, ");
else
Console.Write(i+", ");
}
Console.WriteLine();
}
}
// we have to save the tree before all the n’s occupy the node.
static Dictionary<int, List<__nod> > hm = new Dictionary<int, List<__nod> >();
public static List<__nod> allPossibleFBT(int n)
{
// We must ensure whether the given set of trees exists for the given values of n.
if (!hm.ContainsKey(n)) {
// we have to create a specific list that contains all the nodes.
List<__nod> list = new List<__nod>();
// If N=1, there is only one tree that can exist
// that is the tree that has the root.
if (n == 1) {
list.Add(new __nod(0, NILL, NILL));
}
// We must ensure that the N is odd and the binary tree is full because the tree has N number of nodes.
else if (n % 2 == 1) {
// We must move through all the nodes that can be a part of the left subtree.
for (int x = 0; x < n; x++) {
//The left node will automatically belong to the right subtree.
int y = n - 1 - x;
// we have to move through all the left binary trees by purposely calling it for the function.
for each (__nod Lft in allPossibleFBT(x)) {
// we have to move through all the right binary trees by purposely calling them for the function.
for each (__nod Rt in allPossibleFBT(y)) {
//creating a brand-new node
__nod __nod = new __nod(0, NILL, NILL);
// make the changes in the left node.
__nod.Lft = Lft;
// make the changes in the right node.
__nod.Rt = Rt;
// We have to add that particular node to the list.
list.Add(__nod);
}
}
}
}
//Insert tree in Dictionary.
hm.Add(n, list);
}
return hm[n];
}
}
```

**Output:**

**Example 3)**

```
// Writing the implementation of the above approach in Java.
import java.util.*;
import java.io.*;
class TFT {
// We are creating a class that will create a node and its left and right child.
public static class __nod {
int record;
__nod Lft;
__nod Rt;
__nod(int record, __nod Lft, __nod Rt)
{
this.record = record;
this.Lft = Lft;
this.Rt = Rt;
}
}
// We are creating a new function that will help us traverse the tree and extract all the left and right child that is currently in the list.
public static void display(__nod __nod, List<Integer> al)
{
// If the node turns out to be equal to NILL, then we have to terminate that specific function.
if (__nod == NILL) {
return;
}
// If we have a left child, which is supposed to be part of the node, then we have to insert it into the list
if (__nod.Lft != NILL) {
al.add(__nod.Lft.record);
}
// Or we can insert NILL in the list and head back
else {
al.add(NILL);
}
// Similarly, if we have the right child consisting of a node, then we have to insert it into the list.
if (__nod.Rt != NILL) {
al.add(__nod.Rt.record);
}
// Or we can insert NILL in the list.
else {
al.add(NILL);
}
// We have to repeatedly call that specific function from the left and right child of the particular node and display the function.
display(__nod.Lft, al);
display(__nod.Rt, al);
}
// Writing the main code to test the above functions
public static void main(String[] args)
{
// collecting the input from the source
int n = 7;
// calling the function
List<__nod> list = allPossibleFBT(n);
// we have to print all the possible outcomes of the full binary tree.
for (__nod root: list) {
List<Integer> al = new ArrayList<>();
al.add(root.record);
display(root, al);
System.out.println(al);
}
}
// we have to save the tree before all the n’s occupy the node.
static HashMap<Integer, List<__nod> > hm = new HashMap<>();
public static List<__nod> allPossibleFBT(int n)
{
// We must ensure whether the given set of trees exists for the given values of n.
if (!hm.containsKey(n)) {
// we have to create a specific list that contains all the nodes.
List<__nod> list = new LinkedList<>();
// If N=1, there is only one tree that can exist
// that is the tree that has the root.
if (n == 1) {
list.add(new __nod(0, NILL, NILL));
}
// We must ensure that the N is odd and the binary tree is full because the tree has N number of nodes.
else if (n % 2 == 1) {
// We must move through all the nodes that can be a part of the left subtree.
for (int x = 0; x < n; x++) {
//The left node will automatically belong to the right subtree.
int y = n - 1 - x;
// we have to move through all the left binary trees by purposely calling it for the function.
for (__nod Lft: allPossibleFBT(x)) {
// we have to move through all the right binary trees by purposely calling them for the function.
for (__nod Rt: allPossibleFBT(y)) {
//creating a brand-new node
__nod __nod = new __nod(0, NILL, NILL);
// make the changes in the left node.
__nod.Lft = Lft;
// make the changes in the right node.
__nod.Rt = Rt;
// We have to add that particular node to the list.
list.add(__nod);
}
}
}
}
//We have to insert the tree in a HashMap.
hm.put(n, list);
}
return hm.get(n);
}
}
```

**Output:**

**Example 4)**

```
# Writing the implementation of the above approach in Python
import sys
# We are creating a class that will create a node and its left and right child.
class __nod:
def __init__(self, record, Lft, Rt):
self.record = record
self.Lft = Lft
self.Rt = Rt
# We are creating a new function that will help us traverse the tree and extract all the left and right child that is currently in the list.
def display(__nod, al):
# If the node turns out to be equal to NILL, then we have to terminate that specific function.
if (__nod == None):
return
# If we have a left child, which is supposed to be part of the node, then we have to insert it into the list
if (__nod.Lft != None):
al.append(__nod.Lft.record)
# Or we can insert NILL in the list and head back
else:
al.append(-sys.maxsize)
# Similarly, if we have the right child consisting of a node, we must insert it into the list.
if (__nod.Rt != None):
al.append(__nod.Rt.record)
# Or we can insert NILL in the list.
else:
al.append(-sys.maxsize)
# We have to repeatedly call that specific function from the left and right child of the particular node and display the function.
display(__nod.Lft, al)
display(__nod.Rt, al)
# we have to save the tree before all the n's occupy the node.
hm = {}
def allPossibleFBT(n):
# We have to make sure that whether the given set of trees exists for the given set of values of n or not.
if n not in hm:
# we have to create a specific list that contains all the nodes.
List = []
# If N=1, there is only one tree that can exist
# that is the tree that has the root.
if (n == 1):
List.append(__nod(0, None, None))
# We must ensure that the N is odd and the binary tree is full because the tree has N number of nodes.
elif (n % 2 == 1):
# We must move through all the nodes that can be a part of the left subtree.
for x in range(n):
# the node which is left will automatically belong to the right subtree.
y = n - 1 - x
# We must move through all the left binary trees by purposely calling them for the function.
xallPossibleFBT = allPossibleFBT(x)
yallPossibleFBT = allPossibleFBT(y)
for Lft in range(len(xallPossibleFBT)):
# we have to move through all the right binary trees by purposely calling them for the function.
for Rt in range(len(yallPossibleFBT)):
# Creating a brand-new node
__nod = __nod(0, None, None)
# make the changes in the left node.
__nod.Lft = xallPossibleFBT[Lft]
# make the changes in the right node.
__nod.Rt = yallPossibleFBT[Rt]
# We have to add that particular node to the list.
List.append(__nod)
#Insert tree in Dictionary.
hm[n] = List
return hm[n]
# Collecting the input from the source
n = 7
# Calling the function
List = allPossibleFBT(n)
# We have to print all the possible outcomes of the full binary tree.
for root in range(len(List)):
al = []
al.append(List[root].record)
display(List[root], al)
print("[", end = "")
for i in range(len(al)):
if(i != len(al) - 1):
if(al[i]==-sys.maxsize):
print("NILL, ", end = "")
else:
print(al[i], end = ", ")
else:
if(al[i]==-sys.maxsize):
print("NILL]", end = "")
else:
print(al[i], end = "]")
print()
```

**Output:**

**Example 5)**

```
<script>
// Writing the implementation of the above approach in Javascript.
// We are creating a class that will create a node and its left and right child.
class __nod
{
constructor(record, Lft, Rt) {
this.Lft = Lft;
this.Rt = Rt;
this.record = record;
}
}
// We are creating a new function that will help us traverse the tree and extract all the left and right child that is currently in the list.
function display(__nod, al)
{
// If the node turns out to be equal to NILL, then we have to terminate that specific function.
if (__nod == NILL) {
return;
}
// If we have a left child, which is supposed to be part of the node, then we have to insert it into the list
if (__nod.Lft != NILL) {
al.push(__nod.Lft.record);
}
// Or we can insert NILL in the list and head back
else {
al.push(Number.MIN_VALUE);
}
// Similarly, if we have the right child consisting of a node, then we have to insert it into the list.
if (__nod.Rt != NILL) {
al.push(__nod.Rt.record);
}
// Or we can insert NILL in the list.
else {
al.push(Number.MIN_VALUE);
}
// We have to repeatedly call that specific function from the left and right child of the particular node and display the function.
display(__nod.Lft, al);
display(__nod.Rt, al);
}
// Save tree for all n before recursion.
let hm = new Map();
function allPossibleFBT(n)
{
// We must ensure whether the given set of trees exists for the given values of n.
if (!hm.has(n)) {
// we have to create a specific list that contains all the nodes.
let list = [];
// If N=1, there is only one tree that can exist
// that is the tree that has the root.
if (n == 1) {
list.push(new __nod(0, NILL, NILL));
}
// We must ensure that the N is odd and the binary tree is full because the tree has N number of nodes.
else if (n % 2 == 1) {
// We must move through all the nodes that can be a part of the left subtree.
for (let x = 0; x < n; x++) {
//The left node will automatically belong to the right subtree.
let y = n - 1 - x;
// we have to move through all the left binary trees by purposely calling it for the function.
let xallPossibleFBT = allPossibleFBT(x);
let yallPossibleFBT = allPossibleFBT(y);
for(let Lft = 0; Lft < xallPossibleFBT.length; Lft++) {
// we have to move through all the right binary trees by purposely calling them for the function.
for(let Rt = 0; Rt < yallPossibleFBT.length; Rt++) {
//creating a brand-new node
let __nod = new __nod(0, NILL, NILL);
// make the changes in the left node.
__nod.Lft = xallPossibleFBT[Lft];
// make the changes in the right node.
__nod.Rt = yallPossibleFBT[Rt];
// We have to add that particular node to the list.
list.push(__nod);
}
}
}
}
//Insert tree in Dictionary.
hm.set(n, list);
}
return hm.get(n);
}
// collecting the input from the source
let n = 7;
// calling the function
let list = allPossibleFBT(n);
// we have to print all the possible outcomes of the full binary tree.
for(let root = 0; root < list.length; root++) {
let al = [];
al.push(list[root].record);
display(list[root], al);
document.write("[");
for(let i = 0; i < al.length; i++){
if(i != al.length - 1)
{
if(al[i]==Number.MIN_VALUE)
document.write("NILL, ");
else
document.write(al[i]+ ", ");
}
else{
if(al[i]==Number.MIN_VALUE)
document.write("NILL]");
else
document.write(al[i]+ "]");
}
}
document.write("</br>");
}
</script>
```

**Output:**