Strictly Binary Tree in Data Structures 🌳

A Strictly Binary Tree (also known as a Proper Binary Tree) is a type of Binary Tree where every node has either 0 or 2 children. This means:
✔ No node has only one child
✔ Each internal node has exactly two children
✔ Leaf nodes (nodes with no children) exist only at the last level

---

📌 Example of a Strictly Binary Tree

Tree Structure:

        10
       /  \
      20   30
     /  \   /  \
    40   50 60  70

🔹 Every node has either 0 or 2 children.

❌ Not a Strictly Binary Tree:

        10
       /  
      20   
     /  \
    40   50

🔹 The node 10 has only one child, so this is not a Strictly Binary Tree.

---

📌 Properties of a Strictly Binary Tree

1️⃣ Total Nodes Relation:

• If a Strictly Binary Tree has n internal nodes, then it has exactly n + 1 leaf nodes.
• Formula: $$L = I + 1$$ where L = Number of Leaf Nodes, I = Number of Internal Nodes

2️⃣ Total Nodes Calculation:

• If a Strictly Binary Tree has n leaf nodes, then the total number of nodes T is: $$T = 2L - 1$$
• Example: If a Strictly Binary Tree has 5 leaf nodes, total nodes: $$T = 2(5) - 1 = 9$$

3️⃣ Height of a Strictly Binary Tree:

• A Strictly Binary Tree of height h has a minimum of 2h+1 - 1 nodes.
• Example: For height h = 3: $$\text{Minimum Nodes} = 2(3+1) - 1 = 15$$

---

📌 Code Implementation (C Example)

#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 Strictly Binary
int isStrictlyBinary(struct Node* root) {
    if (root == NULL) return 1;  // Empty tree is considered strictly binary

    // If the node has only one child, it is not strictly binary
    if ((root->left == NULL && root->right != NULL) ||
        (root->left != NULL && root->right == NULL))
        return 0;

    // Recursively check left and right subtrees
    return isStrictlyBinary(root->left) && isStrictlyBinary(root->right);
}

int main() {
    // Creating a Strictly Binary Tree
    struct Node* root = createNode(10);
    root->left = createNode(20);
    root->right = createNode(30);
    root->left->left = createNode(40);
    root->left->right = createNode(50);
    root->right->left = createNode(60);
    root->right->right = createNode(70);

    if (isStrictlyBinary(root))
        printf("The tree is a Strictly Binary Tree.\n");
    else
        printf("The tree is NOT a Strictly Binary Tree.\n");

    return 0;
}

🔹 Output:

The tree is a Strictly Binary Tree.

---

📌 Advantages of a Strictly Binary Tree

✅ Balanced Tree Structure → Leads to better performance in tree operations.
✅ Predictable Structure → Can be used for efficient memory allocation.
✅ Ideal for Tree Traversal Algorithms like Preorder, Inorder, and Postorder.

📌 Disadvantages

❌ Less Flexible → Not suitable for all applications (unlike general binary trees).
❌ Strict Conditions → Every node must have either 0 or 2 children, making insertion operations restrictive.

---

📌 Where is a Strictly Binary Tree Used?

✔ Expression Trees – Used in evaluating mathematical expressions.
✔ Decision Trees – Used in AI for logical decision-making.
✔ Game Trees (Minimax Algorithm) – Used in AI for games like Chess.
✔ Huffman Trees – Used in data compression algorithms (Huffman Encoding).

🌲 Strictly Binary Trees are a fundamental part of computer science and efficient hierarchical data structures