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: