worldofitech
In this tutorial, you will learn about the perfect binary tree. Additionally, you will discover working examples for checking a perfect binary tree in C, C++, Java, and Python.
Perfect Binary Tree → In a perfect binary tree, each leaf is at a similar level and all the inside nodes have two children.
A perfect binary tree is a sort of binary tree wherein each internal node has precisely two child nodes and all the leaf nodes are at a similar level.
All the inner nodes have a level of 2.
Recursively, a perfect binary tree can be characterized as:
- In the event that a single node has no children, it is a perfect binary tree of height h = 0,
2. On the off chance that a node has h > 0, it is a perfect binary tree if both of its subtrees are of height h – 1 and are non-overlapping.
Python, Java, and C/C++ Examples
The following code is for checking whether a tree is a perfect binary tree.
Python
# 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")
Java
// 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");
}
}
C
// 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");
}
C++
// 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";
}
Perfect Binary Tree Theorems
- A perfect binary tree of height h has
2h + 1 – 1node. - 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 normal profundity of a node in a perfect binary tree is Θ(ln(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.
