Logo
×

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:

A Full Binary Tree with n Nodes

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:

A Full Binary Tree with n Nodes

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:

A Full Binary Tree with n Nodes

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:

A Full Binary Tree with n Nodes

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:

A Full Binary Tree with n Nodes

Related Topics

Queue operations in Data Structure

Queue - Queue is a linear data structure or first in first out data structure means the first element added in the queue will be removed first and the last...

7 minutes read.

Does Overloading Work with Inheritance

This is a question that occasionally comes to many programmers. Who are curious to know more now has a complete explanation and a solution through this tutorial! Inheritance: The functions of...

3 minutes read.

Deletion Operation from A B Tree

This article will show the deletion operation through the b tree in C++ programming language. Implementation #include <iostream> using namespace std; class B_TreeNod {   int *kys;   int m;   BTreeNod **C;   int j;   bool leaf;  ...

5 minutes read.

Counting Sort

Counting Sort: Counting sort is a sorting algorithm that is used to sort the elements of the array within a specific range. It counts the same element number of the...

3 minutes read.

What is an AVL Tree in Data Structure?

AVL tree stands for (Adelson, Velskii, & Landis Tree) Data structure Data management is called database management. A data model is a system used to store, manage, and optimize computer resources. Data...

4 minutes read.

Vertical Order Traversal of Binary Tree

Implementation #include <iostream> #include <vector> #include <map> using namespace std; // representing the primary model of a binary tree node. struct _nod { int ky; _nod *Lft, *Rt; }; // establishing a new function representing the new binary tree node. struct _nod*...

5 minutes read.

Counts the number of times a given element occurs in a Linked List

Counts the number of times a given element occurs in a Linked List This article will explain how we can count the occurrences of a particular element in a list. Here,...

3 minutes read.

Finding the Maximum Element in a Binary Tree

Implementation // Creating a C++ program to excavate the minimum and maximum in a given binary tree. #include <bits/stdc++.h> #include <iostream> using namespace std; // creating a new tree node. class __nod { public: int record; __nod *Lft, *Rt; /*...

4 minutes read.

What is the difference between Tree and Graph

We usually use a diverse range of data structure to store our data and information. To store them in a more sequential manner and to access them easily, we use...

4 minutes read.

Permutation Sort or Bogo Sort

In Permutation Sort or Bogo Sort, you have been given one array, which consists of different values. You have to sort the array using BOGO sort. Let’s take an example: Input-...

3 minutes read.

Digital Search Tree in Data Structures

What is a digital search Tree in Data Structures? The Digital search tree is known for its application and diversity in the way it has impacted our world in the field...

3 minutes read.

Stack Using Linked List

In the linked list implementation of the stack, we use a linked list as the primitive data structure to create the stack. It is called the dynamic implementation of the...

6 minutes read.

Binary Tree Inorder Traversal

The binary tree is a type of tree in which each and every node has atleast two children except the leaf nodes. We have various operations in the binary tree,...

4 minutes read.

Binary Tree to Doubly Linked List

Binary Tree to Doubly Linked List This article will explain how to convert the given binary tree into a Doubly Linked List. The left and right pointers in tree nodes are...

2 minutes read.

Hashing

Hashing: Hashing is a process in which a large amount of data is mapped to a small table with the help of hashing function. It is a searching technique. Hash table We...

4 minutes read.

Binary Tree Implementation Using Arrays

Implementation Converting a binary tree into a list of arrays is one interesting problem. Let us see that in depth. In this section, we will see the implementation of the binary Trees...

4 minutes read.

Heap Sort vs Merge Sort

In this article, we are going to discuss the Heap Sort, Merge sort and the difference between them. What is Heap Sort? Heap – A heap is an abstract data type categorised...

7 minutes read.

Trie data structure

Trie data structure The term “trie” comes from the word “retrieval” which means getting information. The trie data structure is a sorted extension of tree-based data structure. The trie data structure...

5 minutes read.

Function to Delete a Leaf Node from a Binary Tree

Implementation // We are writing a C++ code to eliminate all the leaves from the given value.  #include <bits/stdc++.h> using namespace std; // creating a new binary tree node struct __nod { int record; struct __nod *Lft,...

4 minutes read.

DFS (Depth-first search) Algorithm: Data Structure

What is DFS (Depth-first search)? The depth first search is a graph traversal algorithm. The idea behind this algorithm is backtracking and it is a kind of recursive algorithm. In the...

3 minutes read.