 Full Binary Tree

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

``````# 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")
``````
``````// 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 full\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 full\n";
}``````