A Perfect Binary Tree is a type of binary tree in which every internal node has exactly two children and all the leaf nodes are at the same level. This structure ensures that the tree is completely filled at every level except possibly for the last level, which is filled from left to right.


class Node {
    int data;
    Node left, right;
 
    Node(int item) {
        data = item;
        left = right = null;
    }
}
 
class PerfectBinaryTree {
    Node root;
 
    boolean isPerfect(Node root, int d, int level) {
        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 isPerfect(root.left, d, level + 1) &&
               isPerfect(root.right, d, level + 1);
    }
 
    int depth(Node node) {
        int d = 0;
        while (node != null) {
            d++;
            node = node.left;
        }
        return d;
    }
 
    boolean isPerfect(Node root) {
        int d = depth(root);
        return isPerfect(root, d, 0);
    }
}

Properties:

1. The number of nodes at level ‘l’ is 2^l.

2. Total number of nodes in a perfect binary tree of height h is 2^(h+1) - 1.

3. The height of a perfect binary tree with n nodes is log2(n+1) - 1.

Console Output:

The tree is perfect

Level Order Traversal

Traversal Explanation:

Level order traversal of a perfect binary tree visits nodes level by level, starting from the root and moving downwards. This traversal method is particularly efficient for perfect binary trees due to their complete structure.


import java.util.LinkedList;
import java.util.Queue;
 
class LevelOrderTraversal {
    Node root;
 
    void printLevelOrder() {
        Queue queue = new LinkedList();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node tempNode = queue.poll();
            System.out.print(tempNode.data + " ");
 
            if (tempNode.left != null)
                queue.add(tempNode.left);
 
            if (tempNode.right != null)
                queue.add(tempNode.right);
        }
    }
}

Benefits:

Level order traversal is beneficial for breadth-first processing of nodes, which is useful in scenarios like finding the shortest path in an unweighted graph represented as a tree.

Console Output:

1 2 3 4 5 6 7

Height Calculation

Height of a Perfect Binary Tree:

The height of a perfect binary tree can be calculated using the formula: height = log2(n+1) - 1, where n is the number of nodes. This formula arises from the complete filling of levels in a perfect binary tree.


class TreeHeight {
    Node root;
 
    int calculateHeight(Node node) {
        if (node == null)
            return -1;
        else {
            int leftHeight = calculateHeight(node.left);
            int rightHeight = calculateHeight(node.right);
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }
}

Use Case:

Knowing the height of a tree is essential for understanding its depth and is crucial for operations like balancing the tree or calculating its diameter.

Console Output:

Height of the tree is 2

Insertion in Perfect Binary Tree

Insertion Process:

In a perfect binary tree, insertion is typically done level by level from left to right. This ensures that all levels are completely filled before moving to the next.


import java.util.LinkedList;
import java.util.Queue;
 
class InsertNode {
    Node root;
 
    void insert(int key) {
        Node newNode = new Node(key);
        if (root == null) {
            root = newNode;
            return;
        }
 
        Queue q = new LinkedList();
        q.add(root);
 
        while (!q.isEmpty()) {
            Node temp = q.poll();
 
            if (temp.left == null) {
                temp.left = newNode;
                break;
            } else
                q.add(temp.left);
 
            if (temp.right == null) {
                temp.right = newNode;
                break;
            } else
                q.add(temp.right);
        }
    }
}

Advantages:

This method of insertion maintains the properties of a perfect binary tree, ensuring balance and optimal performance for search operations.

Console Output:

Node inserted at the correct position

Deletion in Perfect Binary Tree

Deletion Process:

Deletion in a perfect binary tree involves removing a node and ensuring the tree remains balanced. Typically, the deepest and rightmost node is removed to maintain the tree's structure.


import java.util.LinkedList;
import java.util.Queue;
 
class DeleteNode {
    Node root;
 
    void deleteDeepest(Node delNode) {
        Queue q = new LinkedList();
        q.add(root);
 
        Node temp = null;
        while (!q.isEmpty()) {
            temp = q.poll();
 
            if (temp == delNode) {
                temp = null;
                return;
            }
            if (temp.right != null) {
                if (temp.right == delNode) {
                    temp.right = null;
                    return;
                } else
                    q.add(temp.right);
            }
 
            if (temp.left != null) {
                if (temp.left == delNode) {
                    temp.left = null;
                    return;
                } else
                    q.add(temp.left);
            }
        }
    }
 
    void delete(int key) {
        if (root == null)
            return;
 
        if (root.left == null && root.right == null) {
            if (root.data == key) {
                root = null;
                return;
            } else
                return;
        }
 
        Queue q = new LinkedList();
        q.add(root);
        Node temp = null, keyNode = null;
 
        while (!q.isEmpty()) {
            temp = q.poll();
 
            if (temp.data == key)
                keyNode = temp;
 
            if (temp.left != null)
                q.add(temp.left);
 
            if (temp.right != null)
                q.add(temp.right);
        }
 
        if (keyNode != null) {
            int x = temp.data;
            deleteDeepest(temp);
            keyNode.data = x;
        }
    }
}

Challenges:

Maintaining the perfect structure after deletion is challenging and may require additional rebalancing steps.

Console Output:

Node deleted successfully