Complete Binary Tree in Data Structures 🌳

A Complete Binary Tree (CBT) is a type of Binary Tree where:
✔ All levels except possibly the last are completely filled.
✔ All nodes are as left-aligned as possible on the last level.

---

📌 Example of a Complete Binary Tree

✅ Valid Complete Binary Tree:

        1
       / \
      2   3
     / \  /
    4   5 6

🔹 All levels except the last are completely filled.
🔹 The last level is filled from left to right.

❌ Not a Complete Binary Tree:

        1
       / \
      2   3
     /    / \
    4    5   6

🔹 The node 5 should have been placed before 3's right child.
🔹 Nodes must be left-aligned on the last level.

---

📌 Properties of a Complete Binary Tree

1️⃣ Height of a Complete Binary Tree:

• For n nodes, the height h is: $$h = \lfloor \log_2{n} \rfloor$$
• Example: If n = 6, then $$h = \lfloor \log_2{6} \rfloor = 2$$

2️⃣ Number of Nodes:

• A complete binary tree with height h has at most: $$2^{h+1} - 1$$
• Example: If height h = 2, max nodes = $$2^{2+1} - 1 = 7$$

3️⃣ Efficient Storage in Arrays:

• A Complete Binary Tree is ideal for Array Representation, since we can use index calculations:

  
  Parent(i) = (i - 1) / 2
  Left Child(i) = 2 * i + 1
  Right Child(i) = 2 * i + 2
  

---

📌 Complete Binary Tree Representation in C

#include <stdio.h>
#include <stdlib.h>

// Define a Node structure
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Function to create a new node
struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// Function to check if a tree is a Complete Binary Tree
int countNodes(struct Node* root) {
    if (root == NULL) return 0;
    return 1 + countNodes(root->left) + countNodes(root->right);
}

int isComplete(struct Node* root, int index, int totalNodes) {
    if (root == NULL) return 1;
    if (index >= totalNodes) return 0;
    return isComplete(root->left, 2 * index + 1, totalNodes) &&
           isComplete(root->right, 2 * index + 2, totalNodes);
}

int main() {
    struct Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);

    int totalNodes = countNodes(root);
    if (isComplete(root, 0, totalNodes))
        printf("The tree is a Complete Binary Tree.\n");
    else
        printf("The tree is NOT a Complete Binary Tree.\n");

    return 0;
}

🔹 Output:

The tree is a Complete Binary Tree.

---

📌 Advantages of a Complete Binary Tree

✅ Efficient Memory Usage – No wasted space like in sparse trees.
✅ Ideal for Heaps & Priority Queues – Used in Heap Sort & Dijkstra’s Algorithm.
✅ Easier Level-Order Traversal – Can be efficiently stored in an array.

📌 Disadvantages

❌ Insertion at the Last Level – Requires maintaining a queue or array indexing.
❌ Not Always Height Balanced – May still need balancing for some applications.

---

📌 Where is a Complete Binary Tree Used?

✔ Binary Heaps – Used in heap-based sorting & scheduling algorithms.
✔ Priority Queues – Implemented using Min/Max Heap structures.
✔ Huffman Coding Trees – Used in compression algorithms.

🌲 Complete Binary Trees are widely used in efficient data structures & algorithms