Table of Contents
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.
1. 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
.
2. Python, Java and C/C++ Examples
The following code is for checking if a tree is a full binary tree.
Source code by Python Language:
# 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")
Source code by Java Language:
// 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"); } }
Source code by C Language:
// 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"); }
Source code by C++ Language:
// 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"; }
Related posts:
Insertion on a B+ Tree
AVL Tree
Bellman Ford's Algorithm
Counting Sort Algorithm
Queue Data Structure
Deletion from a B-tree
Selection Sort Algorithm
Linear Search
Types of Queues
Dijkstra's Algorithm
Insertion into a B-tree
Data Structure and Types
Bubble Sort
Longest Common Subsequence
Breadth first search
Master Theorem
Tree Traversal - inorder, preorder and postorder
Adjacency Matrix
Rabin-Karp Algorithm
Ford-Fulkerson Algorithm
Depth First Search (DFS)
Insertion in a Red-Black Tree
Huffman Coding
Balanced Binary Tree
Backtracking Algorithm
Heap Sort Algorithm
Graph Data Stucture
Radix Sort Algorithm
Binary Search
Decrease Key and Delete Node Operations on a Fibonacci Heap
Heap Data Structure
Spanning Tree and Minimum Spanning Tree