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

Bottom view of the binary tree

The bottom of the binary tree is generally defined as the number of nods present in the bottom-most part of the tree. In this article, we will see the implementation...

3 minutes read.

Stack vs Heap Memory Allocation Data Structure

Difference Between Stack and Heap Memory Allocation Stack Memory Stack memory allocation is a way to use the system memory as a temporary storage of the data which is act like last-in-first-out...

3 minutes read.

Delete N nodes after M nodes of a linked list

Delete N nodes after M nodes of a linked list In this problem, we have given a linked list and two integers M and N. We need to traverse the linked...

3 minutes read.

Linked List Representation of Binary Tree

As we all know, a binary tree has a maximum of two children and helps us manage the info correctly. The word binary itself represents its meaning; we know that...

4 minutes read.

What Is Graph Data Structure

A graph is generally a set of vertices and edges or border that is mainly used to join these vertices. A graph is basically pictured as a cyclic tree in...

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

Length of longest palindrome in a linked list using O(1) extra space

Length of longest palindrome in a linked list using O(1) extra space In this problem, we need to find the length of the longest palindrome list that is present in given...

2 minutes read.

Cycle sort

Cycle sort is an examination arranging calculation which powers exhibit to be figured into the quantity of cycles where every one of them can be pivoted to create an arranged...

5 minutes read.

Remove duplicates from an unsorted Linked List

Remove duplicates from an unsorted Linked List This article will explain how we can remove duplicates from unsorted linked lists. Here we have given an unsorted singly linked list and will...

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.

Binary tree insertion

As we all know, a binary tree has a maximum of two children and helps us manage the info correctly. Here the name of the tree itself portrays the mechanism...

4 minutes read.

Application of 2D array - Sparse Matrix

2D Arrays Application - Sparse Matrix A matrix is a two-dimensional data item consisting of m rows and n columns, with a total of m x n values. A sparse matrix...

7 minutes read.

Rotate a Singly Linked List

Rotate a Singly Linked List This article will explain how we can rotate the singly linked list. Here we have given a singly linked list, and we need to rotate this...

4 minutes read.

Data Structure Infix to Prefix Conversion

Infix to Prefix Conversion In present time, we use the infix expression in our daily life but the computers are not able to understand this format because they need to keep...

4 minutes read.

Recursion in Fibonacci

Fibonacci heap is considered to be a particular execution of the heap data structure that ultimately helps in making use of not just any number but the Fibonacci numbers. It...

3 minutes read.

Hash Table vs STL Map

Hash table and STL map are extremely valuable information structures in software engineering. Here we will consider the examination between their properties to be well as execution.  To start with, we will...

7 minutes read.

Flatten Binary Tree to a linked list

Implementation In this section, we will see the implementation of the binary Tree and its conversion into linked lists. let us proceed: - // Writing a C++ program that will convert a...

4 minutes read.

Arrange consonants and vowels nodes in a linked list

Arrange consonants and vowels nodes in a linked list In this problem, we have given a singly linked list. Here we will arrange the consonants and vowels nodes of the list...

2 minutes read.

Lowest common ancestor in a binary search tree

Suppose you have given two values of nodes in a binary search tree. You have to find out the lowest common ancestor between the nodes. Let’s take an example tree- For the...

4 minutes read.

What is the B+ Tree in Data Structures?

We all know that the B+ tree in data structures is nothing but just an extended version of the B tree. It allows the smooth working of all the operations...

7 minutes read.