Algorithm
A perfect binary tree is a type of binary tree in which all the internal nodes have exactly two children, and all leaf nodes are at the same level or depth. In other words, every level of the tree is completely filled with nodes, and all leaf nodes are at the same level, making the tree balanced.
Key properties of a perfect binary tree:
-
Nodes and Levels:
- At each level of the tree, there are 2^n nodes, where "n" is the level number (starting from level 0 at the root).
- The total number of nodes in a perfect binary tree with height 'h' is 2^(h+1) - 1.
-
Balanced Structure:
- The tree is balanced because every leaf node is at the same depth, and the height of the tree is logâ‚‚(n+1), where "n" is the number of leaf nodes.
-
Number of Nodes:
- If a perfect binary tree has 'h' levels, it will have a total of 2^(h+1) - 1 nodes.
-
Parent-Child Relationship:
- If a node is at index 'i' in the tree, its left child is at index 2i + 1, and its right child is at index 2i + 2.
Here is an example of a perfect binary tree:
markdown
1
/ \
2 3
/ \ / \
4 5 6 7
In this example, the tree has three levels, and each level is completely filled with nodes. The leaf nodes (4, 5, 6, 7) are all at the same level, making it a perfect binary tree.
Code Examples
#1 Perfect Binary Tree implement in Python
Code -
Python Programming
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def build_perfect_binary_tree(depth):
if depth <= 0:
return None
root = Node(1)
root.left = build_perfect_binary_tree(depth - 1)
root.right = build_perfect_binary_tree(depth - 1)
return root
def print_tree(root, level=0, prefix="Root: "):
if root is not None:
print(" " * (level * 4) + prefix + str(root.key))
if root.left is not None or root.right is not None:
print_tree(root.left, level + 1, "L--- ")
print_tree(root.right, level + 1, "R--- ")
# Example usage:
depth_of_tree = 3
perfect_tree = build_perfect_binary_tree(depth_of_tree)
print_tree(perfect_tree)
#2 Perfect Binary Tree implement in Java
Code -
Java Programming
class Node {
int data;
Node left, right;
public Node(int item) {
data = item;
left = right = null;
}
}
public class PerfectBinaryTree {
Node root;
// Constructor
public PerfectBinaryTree() {
root = null;
}
// Function to insert a new node
public void insert(int data) {
root = insertRec(root, data);
}
// A recursive function to insert a new node with a given data
private Node insertRec(Node root, int data) {
if (root == null) {
root = new Node(data);
return root;
}
if (data < root.data) {
root.left = insertRec(root.left, data);
} else if (data > root.data) {
root.right = insertRec(root.right, data);
}
return root;
}
// Function to print the tree in an inorder traversal
public void inorder() {
inorderRec(root);
}
// A utility function to do inorder traversal of the tree
private void inorderRec(Node root) {
if (root != null) {
inorderRec(root.left);
System.out.print(root.data + " ");
inorderRec(root.right);
}
}
public static void main(String[] args) {
PerfectBinaryTree tree = new PerfectBinaryTree();
// Inserting nodes
tree.insert(50);
tree.insert(30);
tree.insert(70);
tree.insert(20);
tree.insert(40);
tree.insert(60);
tree.insert(80);
// Print inorder traversal
System.out.println("Inorder traversal:");
tree.inorder();
}
}
#3 Perfect Binary Tree implement in C
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
// Define the structure for a binary tree node
typedef struct Node {
int data;
struct Node *left;
struct Node *right;
} Node;
// Function to create a new node
Node *createNode(int data) {
Node *newNode = (Node *)malloc(sizeof(Node));
if (newNode == NULL) {
perror("Failed to allocate memory for the new node");
exit(EXIT_FAILURE);
}
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// Function to build a perfect binary tree of given height
Node *buildPerfectBinaryTree(int height, int value) {
if (height == 0) {
return NULL;
}
Node *root = createNode(value);
root->left = buildPerfectBinaryTree(height - 1, 2 * value);
root->right = buildPerfectBinaryTree(height - 1, 2 * value + 1);
return root;
}
// Function to print the inorder traversal of the tree
void inorderTraversal(Node *root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
}
// Function to deallocate the memory used by the tree
void freeTree(Node *root) {
if (root != NULL) {
freeTree(root->left);
freeTree(root->right);
free(root);
}
}
int main() {
// Build a perfect binary tree of height 3
Node *root = buildPerfectBinaryTree(3, 1);
// Print the inorder traversal of the tree
printf("Inorder Traversal: ");
inorderTraversal(root);
printf("\n");
// Free the memory used by the tree
freeTree(root);
return 0;
}
#4 Perfect Binary Tree implement in C++
Code -
C++ Programming
#include <iostream>
#include <queue>
// Node structure for the binary tree
struct Node {
int data;
Node* left;
Node* right;
Node(int value) : data(value), left(nullptr), right(nullptr) {}
};
class PerfectBinaryTree {
private:
Node* root;
public:
PerfectBinaryTree() : root(nullptr) {}
// Function to insert a node into the tree
void insert(int value) {
root = insertRecursive(root, value);
}
// Recursive function to insert a node into the tree
Node* insertRecursive(Node* current, int value) {
if (current == nullptr) {
return new Node(value);
}
if (value < current->data) {
current->left = insertRecursive(current->left, value);
} else if (value > current->data) {
current->right = insertRecursive(current->right, value);
}
return current;
}
// Function to perform a level order traversal (BFS) of the tree
void levelOrderTraversal() {
if (root == nullptr) {
std::cout << "Tree is empty." << std::endl;
return;
}
std::queue < Node*> q;
q.push(root);
while (!q.empty()) {
Node* current = q.front();
q.pop();
std::cout << current->data << " ";
if (current->left != nullptr) {
q.push(current->left);
}
if (current->right != nullptr) {
q.push(current->right);
}
}
std::cout << std::endl;
}
};
int main() {
PerfectBinaryTree tree;
// Insert nodes into the tree
tree.insert(5);
tree.insert(3);
tree.insert(7);
tree.insert(2);
tree.insert(4);
tree.insert(6);
tree.insert(8);
// Perform level order traversal
std::cout << "Level Order Traversal: ";
tree.levelOrderTraversal();
return 0;
}
Demonstration
Perfect Binary Tree-DevsEnv