Page Index

Full Binary Tree

In this tutorial, you will learn about full binary tree and its different theorems. Also, you will find working examples to check full binary tree in C, C++, Java and Python.

A full Binary tree is a special type of binary tree in which every parent node/internal node has either two or no children.

It is also known as a proper binary tree.

full binary tree
Full 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
  1. The number of leaves is i + 1.
  2. The total number of nodes is 2i + 1.
  3. The number of internal nodes is (n – 1) / 2.
  4. The number of leaves is (n + 1) / 2.
  5. The total number of nodes is 2l – 1.
  6. The number of internal nodes is l – 1.
  7. 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
Java
C
C++
# 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.leftChild.rightChild.leftChild = Node(6)
root.leftChild.rightChild.rightChild = Node(7)

if isFullTree(root):
print("The tree is a full binary tree")
else:
print("The tree is not a full binary tree")

// 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");
}
}
// 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 tree\n");
}
// 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 tree\n";
}

Table of Contents