In this tutorial, you will learn about the full binary tree and its various theorems. Likewise, you will discover working examples to check full binary trees in C, C++, Java, and Python.
what is a Full Binary Tree?
It is a special sort of binary tree that has either zero children or two children. It implies that all the nodes in that binary tree ought to either have two child nodes of its parent node or the parent node is itself the leaf node or the external node.
As such, a full binary tree is a unique binary tree where each node except the external node has two children. At the point when it holds a single child, a particularly binary tree won’t be a full binary tree. Here, the amount of leaf nodes is equivalent to the number of internal nodes in addition to one. The equation resembles L=I+1, where L is the number of leaf nodes, and I is the number of internal nodes.
A full Binary tree is a special type of binary tree where each parent node/inner node has either two or no children.
It is otherwise called a proper binary tree.
Full Binary Tree Theorems
Let, i = the number of internal nodes
n = be the total number of nodes
l = number of leaves
λ = number of levels
- The number of leaves is i + 1.
- The total number of nodes is 2i + 1.
- The number of internal nodes is (n – 1) / 2.
- The number of leaves is (n + 1) / 2.
- The total number of nodes is 2l – 1.
- The number of internal nodes is l – 1.
- The number of leaves is at most 2λ – 1.
Python, Java, and C/C++ Examples
The following code is for checking if a tree is a full binary tree.
Python
# Checking if a binary tree is a full binary tree in Python
# Creating a node
class Node:
def __init__(self, item):
self.item = item
self.leftChild = None
self.rightChild = None
# Checking full binary tree
def isFullTree(root):
# Tree empty case
if root is None:
return True
# Checking whether child is present
if root.leftChild is None and root.rightChild is None:
return True
if root.leftChild is not None and root.rightChild is not None:
return (isFullTree(root.leftChild) and isFullTree(root.rightChild))
return False
root = Node(1)
root.rightChild = Node(3)
root.leftChild = Node(2)
root.leftChild.leftChild = Node(4)
root.leftChild.rightChild = Node(5)
root.rightChild.leftChild.leftChild = Node(6)
root.rightChild.leftChild.rightChild = Node(7)
if isFullTree(root):
print("The tree is a full binary tree")
else:
print("The tree is not a full binary full")
Java
// Checking if a binary tree is a full binary tree in Java
class Node {
int data;
Node leftChild, rightChild;
Node(int item) {
data = item;
leftChild = rightChild = null;
}
}
class BinaryTree {
Node root;
// Check for Full Binary Tree
boolean isFullBinaryTree(Node node) {
// Checking tree emptiness
if (node == null)
return true;
// Checking the children
if (node.leftChild == null && node.rightChild == null)
return true;
if ((node.leftChild != null) && (node.rightChild != null))
return (isFullBinaryTree(node.leftChild) && isFullBinaryTree(node.rightChild));
return false;
}
public static void main(String args[]) {
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.leftChild = new Node(2);
tree.root.rightChild = new Node(3);
tree.root.leftChild.leftChild = new Node(4);
tree.root.leftChild.rightChild = new Node(5);
tree.root.rightChild.leftChild = new Node(6);
tree.root.rightChild.rightChild = new Node(7);
if (tree.isFullBinaryTree(tree.root))
System.out.print("The tree is a full binary tree");
else
System.out.print("The tree is not a full binary tree");
}
}
C
// Checking if a binary tree is a full binary tree in C
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
struct Node {
int item;
struct Node *left, *right;
};
// Creation of new Node
struct Node *createNewNode(char k) {
struct Node *node = (struct Node *)malloc(sizeof(struct Node));
node->item = k;
node->right = node->left = NULL;
return node;
}
bool isFullBinaryTree(struct Node *root) {
// Checking tree emptiness
if (root == NULL)
return true;
// Checking the presence of children
if (root->left == NULL && root->right == NULL)
return true;
if ((root->left) && (root->right))
return (isFullBinaryTree(root->left) && isFullBinaryTree(root->right));
return false;
}
int main() {
struct Node *root = NULL;
root = createNewNode(1);
root->left = createNewNode(2);
root->right = createNewNode(3);
root->left->left = createNewNode(4);
root->left->right = createNewNode(5);
root->left->right->left = createNewNode(6);
root->left->right->right = createNewNode(7);
if (isFullBinaryTree(root))
printf("The tree is a full binary tree\n");
else
printf("The tree is not a full binary full\n");
}
C++
// Checking if a binary tree is a full binary tree in C++
#include <iostream>
using namespace std;
struct Node {
int key;
struct Node *left, *right;
};
// New node creation
struct Node *newNode(char k) {
struct Node *node = (struct Node *)malloc(sizeof(struct Node));
node->key = k;
node->right = node->left = NULL;
return node;
}
bool isFullBinaryTree(struct Node *root) {
// Checking for emptiness
if (root == NULL)
return true;
// Checking for the presence of children
if (root->left == NULL && root->right == NULL)
return true;
if ((root->left) && (root->right))
return (isFullBinaryTree(root->left) && isFullBinaryTree(root->right));
return false;
}
int main() {
struct Node *root = NULL;
root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->left->right->left = newNode(6);
root->left->right->right = newNode(7);
if (isFullBinaryTree(root))
cout << "The tree is a full binary tree\n";
else
cout << "The tree is not a full binary full\n";
}
Thanks for reading! We hope you found this tutorial helpful and we would love to hear your feedback in the Comments section below. And show us what you’ve learned by sharing your photos and creative projects with us.
