1. Overview
In this tutorial, you will learn about the perfect binary tree. Also, you will find working examples for checking a perfect binary tree in C, C++, Java and Python.
A perfect binary tree is a type of binary tree in which every internal node has exactly two child nodes and all the leaf nodes are at the same level.
All the internal nodes have a degree of 2.
Recursively, a perfect binary tree can be defined as:
- If a single node has no children, it is a perfect binary tree of height
h = 0
, - If a node has
h > 0
, it is a perfect binary tree if both of its subtrees are of heighth - 1
and are non-overlapping.
2. Python, Java and C/C++ Examples
The following code is for checking whether a tree is a perfect binary tree.
Source code by Python Language:
# Checking if a binary tree is a perfect binary tree in Python class newNode: def __init__(self, k): self.key = k self.right = self.left = None # Calculate the depth def calculateDepth(node): d = 0 while (node is not None): d += 1 node = node.left return d # Check if the tree is perfect binary tree def is_perfect(root, d, level=0): # Check if the tree is empty if (root is None): return True # Check the presence of trees if (root.left is None and root.right is None): return (d == level + 1) if (root.left is None or root.right is None): return False return (is_perfect(root.left, d, level + 1) and is_perfect(root.right, d, level + 1)) root = None root = newNode(1) root.left = newNode(2) root.right = newNode(3) root.left.left = newNode(4) root.left.right = newNode(5) if (is_perfect(root, calculateDepth(root))): print("The tree is a perfect binary tree") else: print("The tree is not a perfect binary tree")
Source code by Java Language:
// Checking if a binary tree is a perfect binary tree in Java class PerfectBinaryTree { static class Node { int key; Node left, right; } // Calculate the depth static int depth(Node node) { int d = 0; while (node != null) { d++; node = node.left; } return d; } // Check if the tree is perfect binary tree static boolean is_perfect(Node root, int d, int level) { // Check if the tree is empty if (root == null) return true; // If for children if (root.left == null && root.right == null) return (d == level + 1); if (root.left == null || root.right == null) return false; return is_perfect(root.left, d, level + 1) && is_perfect(root.right, d, level + 1); } // Wrapper function static boolean is_Perfect(Node root) { int d = depth(root); return is_perfect(root, d, 0); } // Create a new node static Node newNode(int k) { Node node = new Node(); node.key = k; node.right = null; node.left = null; return node; } public static void main(String args[]) { Node root = null; root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); if (is_Perfect(root) == true) System.out.println("The tree is a perfect binary tree"); else System.out.println("The tree is not a perfect binary tree"); } }
Source code by C Language:
// Checking if a binary tree is a perfect binary tree in C #include <stdbool.h> #include <stdio.h> #include <stdlib.h> struct node { int data; struct node *left; struct node *right; }; // Creating a new node struct node *newnode(int data) { struct node *node = (struct node *)malloc(sizeof(struct node)); node->data = data; node->left = NULL; node->right = NULL; return (node); } // Calculate the depth int depth(struct node *node) { int d = 0; while (node != NULL) { d++; node = node->left; } return d; } // Check if the tree is perfect bool is_perfect(struct node *root, int d, int level) { // Check if the tree is empty if (root == NULL) return true; // Check the presence of children if (root->left == NULL && root->right == NULL) return (d == level + 1); if (root->left == NULL || root->right == NULL) return false; return is_perfect(root->left, d, level + 1) && is_perfect(root->right, d, level + 1); } // Wrapper function bool is_Perfect(struct node *root) { int d = depth(root); return is_perfect(root, d, 0); } 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->right->left = newnode(6); if (is_Perfect(root)) printf("The tree is a perfect binary tree\n"); else printf("The tree is not a perfect binary tree\n"); }
Source code by C++ Language:
// Checking if a binary tree is a perfect binary tree in C++ #include <iostream> using namespace std; struct Node { int key; struct Node *left, *right; }; int depth(Node *node) { int d = 0; while (node != NULL) { d++; node = node->left; } return d; } bool isPerfectR(struct Node *root, int d, int level = 0) { if (root == NULL) return true; if (root->left == NULL && root->right == NULL) return (d == level + 1); if (root->left == NULL || root->right == NULL) return false; return isPerfectR(root->left, d, level + 1) && isPerfectR(root->right, d, level + 1); } bool isPerfect(Node *root) { int d = depth(root); return isPerfectR(root, d); } struct Node *newNode(int k) { struct Node *node = new Node; node->key = k; node->right = node->left = NULL; return node; } 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->right->left = newNode(6); if (isPerfect(root)) cout << "The tree is a perfect binary tree\n"; else cout << "The tree is not a perfect binary tree\n"; }
3. Perfect Binary Tree Theorems
- A perfect binary tree of height h has
2h + 1 – 1
node. - A perfect binary tree with n nodes has height
log(n + 1) – 1 = Θ(ln(n))
. - A perfect binary tree of height h has
2h
leaf nodes. - The average depth of a node in a perfect binary tree is
Θ(ln(n))
.
Related posts:
Ford-Fulkerson Algorithm
Types of Queues
Rabin-Karp Algorithm
Binary Search Tree (BST)
Linked List Operations: Traverse, Insert and Delete
Insertion into a B-tree
Graph Data Stucture
Breadth first search
Decrease Key and Delete Node Operations on a Fibonacci Heap
Adjacency Matrix
Asymptotic Analysis: Big-O Notation and More
AVL Tree
Circular Queue Data Structure
Divide and Conquer Algorithm
Dynamic Programming
Bucket Sort Algorithm
Linked list Data Structure
Backtracking Algorithm
Data Structure and Types
Dijkstra's Algorithm
Complete Binary Tree
Fibonacci Heap
Kruskal's Algorithm
Strongly Connected Components
Priority Queue
Why Learn Data Structures and Algorithms?
Radix Sort Algorithm
Adjacency List
Hash Table
Binary Search
Tree Data Structure
Selection Sort Algorithm