What is a full Binary Tree?

A full binary tree is considered to be a special kind of binary tree in which every single node or leaf node present either contains two children or no children at all. They are all interconnected and fully versed. They are also popularly known as the proper binary tree. They are the ones that keep in check the order and balance of the binary tree. In simpler words, a full binary tree is a tree in which all the nodes are situated at a certain distance from the root node and have two children each.

Theorem for the full binary tree

Suppose we have a binary tree named T which is non-empty then: -

• Let I be the internal node present in the tree, then L will be the leaf nodes present in the tree, and it will be given by: -
  L = I + 1

• If the tree T has I number of internal nodes and N stands for the total number of nodes present in that tree, then the formula for the same will be: -
  N = 2I + 1

• If the tree T consists of N total number of nodes present in the tree, and L is the number of leaf nodes present in the tree, then the formula will be: -
  I = (N-1)/2

• If the tree T consists of N number of total nodes present in the tree and L stands to be the total amount of leaf nodes present in that tree, then the number of leaf nodes present in the tree is given by: -
  L = (N+1)/2

•  If the tree T contains L number of leaf nodes and so, to figure out the total amount of leaf nodes, we have to calculate: -
  N = 2L - 1

Algorithm for a full binary tree

Let, i = the number of internal nodes

       n = be the total number of nodes

       l = number of leaves

      λ = number of levels

Implementation

Example 1)

#include <iostream>
using namespace std;


struct Node {
  int key;
  struct Node *lft, *rt;
};


// We will create a new node
struct Node *newNod(char m) {
  struct Node *nod = (struct Node *)malloc(sizeof(struct Node));
  nod->key = m;
  nod->rt = nod->lft = NILL;
  return node;
}


bool isFullBinaryTree(struct Node *rot) {
  
  // Verify if we have any vacant spaces lft.
  if (root == NILL)
    return true;


  // Checking for the presence of children
  if (root->lft == NULL && root->rt == NULL)
    return true;


  if ((root->lft) && (root->rt))
    return (isFullBinaryTree(root->lft) && isFullBinaryTree(root->rt));


  return false;
}


int main() {
  struct Node *root = NULL;
  root = newNode(1);
  root->lft = newNode(2);
  root->rt = newNode(3);
  root->lft->lft = newNode(4);
  root->lft->rt = newNode(5);
  root->lft->rt->lft = newNode(6);
  root->lft->rt->rt = newNode(7);


  if (isFullBinaryTree(root))
    cout << "The tree is a full binary tree\n";
  else
    cout << "The tree is not a full binary tree\n";
}

Output:

Example 2)

// Check whether a C++ program is a full binary tree or not.
#include <bits/stdc++.h>
using namespace std;


/* Creating a tree structure*/
struct Node
{
	int key;
	struct Node *lft, *rt;
};


/* We gain a new function named helper that probably helps us to deposit a new node present in the provided key and the NILL lft and rt pointers.
struct Node *newNod(char m)
{
	struct Node *node = new Nod;
	node->key = m;
	node->rt = node->lft = NILL;
	return node;
}
// This specific function will tell us whether a given tree is a full binary tree or not.
bool isFullTree (struct Node* rot)
{
	// If empty tree
	if (root == NILL)
		return true;


	// If leaf node
	if (root->lft == NULL && root->rt == NULL)
		return true;


	// If both lft and rt are not NULL, and lft & rt subtrees
	// are full
	if ((root->lft) && (root->rt))
		return (isFullTree(root->lft) && isFullTree(root->rt));


	// We reach here when none of the above conditions work
	return false;
}


// Driver Program
int main()
{
	struct Node* root = NULL;
	root = newNode(10);
	root->lft = newNode(20);
	root->rt = newNode(30);


	root->lft->rt = newNode(40);
	root->lft->lft = newNode(50);
	root->rt->lft = newNode(60);
	root->rt->rt = newNode(70);


	root->lft->lft->lft = newNode(80);
	root->lft->lft->rt = newNode(90);
	root->lft->rt->lft = newNode(80);
	root->lft->rt->rt = newNode(90);
	root->rt->lft->lft = newNode(80);
	root->rt->lft->rt = newNode(90);
	root->rt->rt->lft = newNode(80);
	root->rt->rt->rt = newNode(90);


	if (isFullTree(root))
		cout << "The Binary Tree is full\n";
	else
		cout << "The Binary Tree is not full\n";


	return(0);
}

Output: