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

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

Binary Search Tree (BST) in Data Structures

 A Binary Search Tree (BST) is a special type of Binary Tree that maintains elements in sorted order. It allows for efficient searching, insertion, and deletion operations.

---

📌 Properties of a Binary Search Tree (BST)

✔ Left Subtree Rule – The left child contains nodes with values less than the parent node.
✔ Right Subtree Rule – The right child contains nodes with values greater than the parent node.
✔ No Duplicate Values – Each value in the BST is unique.
✔ Inorder Traversal Results in Sorted Order – A BST, when traversed in inorder (LNR), returns elements in ascending order.

---

📌 Example of a BST

Tree Structure

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

Array Representation (Level Order)

[50, 30, 70, 20, 40, 60, 80]

• Left of 50 → 30 (less than 50)
• Right of 50 → 70 (greater than 50)
• Left of 30 → 20, Right of 30 → 40
• Left of 70 → 60, Right of 70 → 80

---

📌 Operations on a BST

1️⃣ Searching in BST (O(log n))

• Compare the target value with the root.
• If it’s smaller, search the left subtree; if larger, search the right subtree.
• Repeat until the value is found or the subtree is empty.

🔹 Worst Case (Unbalanced Tree): O(n)
🔹 Best/Average Case (Balanced Tree): O(log n)

---

2️⃣ Insertion in BST (O(log n))

• Start at the root.
• Compare the new value with the root:
  • If smaller, move left.
  • If greater, move right.
• Insert it at the appropriate position when an empty spot is found.

🔹 Example: Inserting 25 in the above tree:

        50
       /  \
     30    70
    /  \   /  \
   20   40 60  80
      \
      25  <-- Inserted Here

---

3️⃣ Deletion in BST (O(log n))

Three cases for deletion:

1. Node with no child → Simply remove it.
2. Node with one child → Replace it with its child.
3. Node with two children → Replace it with its inorder successor (smallest value in the right subtree).

🔹 Example: Deleting 50

• The inorder successor of 50 is 60
• Replace 50 with 60, then delete the original 60

        60
       /  \
     30    70
    /  \      \
   20   40    80

---

📌 BST Code Implementation 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 = newNode->right = NULL;
    return newNode;
}

// Insert a node in BST
struct Node* insert(struct Node* root, int value) {
    if (root == NULL) return createNode(value);
    if (value < root->data)
        root->left = insert(root->left, value);
    else
        root->right = insert(root->right, value);
    return root;
}

// Inorder Traversal (LNR) - Prints elements in sorted order
void inorderTraversal(struct Node* root) {
    if (root == NULL) return;
    inorderTraversal(root->left);
    printf("%d ", root->data);
    inorderTraversal(root->right);
}

int main() {
    struct Node* root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 70);
    insert(root, 20);
    insert(root, 40);
    insert(root, 60);
    insert(root, 80);

    printf("Inorder Traversal of BST: ");
    inorderTraversal(root);
    return 0;
}

🔹 Output:

Inorder Traversal of BST: 20 30 40 50 60 70 80

💡 This confirms that BST maintains elements in sorted order!

---

📌 Advantages of BST

✅ Efficient Searching (O(log n))
✅ Sorted Order Retrieval using Inorder Traversal
✅ Dynamic and Easy to Modify (Insert/Delete)

📌 Disadvantages of BST

❌ Unbalanced Trees Can Become Slow (O(n)) – If elements are inserted in sorted order, the tree becomes skewed.
❌ Balancing Needed – AVL and Red-Black Trees improve efficiency.

---

📌 When to Use a BST?

✔ Efficient Searching & Sorting – Used in databases, maps, and sets.
✔ Hierarchical Data Representation – Used in file systems and routers.
✔ Symbol Tables & Dictionaries – Used in compilers and natural language processing.

🌲 Binary Search Trees are a fundamental data structure for fast searching and efficient data management

Array Representation of Binary Trees

 

Array Representation of Binary Trees 🌳

In Array Representation, a Binary Tree is stored in a sequential manner using an array. This method is most efficient for Complete Binary Trees but can lead to memory wastage in Sparse Trees (trees with missing nodes).

---

📌 Indexing Rules for Array Representation

For a node at index i in an array:
🔹 Parent Node → Stored at index (i - 1) / 2
🔹 Left Child → Stored at index 2 * i + 1
🔹 Right Child → Stored at index 2 * i + 2

---

📌 Example of Array Representation

Tree Structure:

markdown
        10
       /  \
      20   30
     /  \
    40   50

Array Representation:

makefile
Index:  0   1   2   3   4  
Value: [10, 20, 30, 40, 50]

✅ Index Mapping:

• Root (10) → arr[0]
• Left Child of 10 (20) → arr[1] = arr[2*0 + 1]
• Right Child of 10 (30) → arr[2] = arr[2*0 + 2]
• Left Child of 20 (40) → arr[3] = arr[2*1 + 1]
• Right Child of 20 (50) → arr[4] = arr[2*1 + 2]

---

📌 Advantages of Array Representation:

✅ Less memory overhead (no need for pointers).
✅ Fast access using index calculations (O(1) lookup).
✅ Works well for complete & full binary trees.

📌 Disadvantages of Array Representation:

❌ Wastes space for sparse trees (missing nodes still take up space).
❌ Insertion & deletion are expensive (requires shifting elements).

---

📌 When to Use Array Representation?

✔ Efficient for Complete Binary Trees & Heaps (used in Priority Queues).
✔ Not ideal for unbalanced or sparse trees (better to use linked representation).

Binary Tree Representation in Data Structures

 Binary Tree Representation in Data Structures

A Binary Tree can be represented in different ways in memory. The two most common representations are:

---

📌 1. Using Linked Representation (Pointer-Based)

In this method, each node is represented as a structure (or class) containing:
✔ Data – The actual value stored in the node.
✔ Left Pointer – A reference to the left child.
✔ Right Pointer – A reference to the right child.

Example (C-like Representation):

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

💡 Advantages:
✅ Dynamic memory allocation, so space is used efficiently.
✅ Flexible, allowing easy insertion and deletion of nodes.
❌ Slightly more memory required due to pointers.

---

📌 2. Using Array Representation (Sequential Representation)

A Binary Tree can also be stored in an array, especially for Complete Binary Trees.

🔹 Indexing Rules for Array Representation:

• Root node is stored at index 0.
• Left child of node at index i → Stored at index 2*i + 1.
• Right child of node at index i → Stored at index 2*i + 2.
• Parent of node at index i → Stored at index (i-1)/2.

Example (Array Representation of a Binary Tree):

Tree Structure:

        10
       /  \
      20   30
     /  \
    40   50

Array Representation:

Index:  0   1   2   3   4  
Value: [10, 20, 30, 40, 50]

💡 Advantages:
✅ Requires less memory (no need for pointers).
✅ Faster indexing (O(1) access using index calculations).
❌ Not efficient for unbalanced trees (wastes memory for null children).

---

📌 Which Representation to Use?

✔ Use Linked Representation when dealing with dynamic trees (e.g., BSTs).
✔ Use Array Representation when dealing with Complete Binary Trees or Heaps.

Binary Trees in Data Structure

Binary Trees in Data Structure 🌳

A Binary Tree is a hierarchical data structure in which each node has at most two children: a left child and a right child. It is widely used in searching, sorting, and hierarchical data representation.

---

📌 Key Properties of a Binary Tree:

✔ Each node has at most two children (left & right).
✔ The depth of nodes varies, affecting tree height.
✔ Can be balanced or unbalanced.

---

📌 Types of Binary Trees:

1️⃣ Full Binary Tree – Every node has 0 or 2 children (no single-child nodes).
2️⃣ Complete Binary Tree – All levels are completely filled, except possibly the last level, which is filled from left to right.
3️⃣ Perfect Binary Tree – All internal nodes have two children, and all leaf nodes are at the same level.
4️⃣ Balanced Binary Tree – The height difference between left and right subtrees is at most 1 (e.g., AVL Tree).
5️⃣ Degenerate (Skewed) Tree – Each parent node has only one child, making it look like a linked list.

---

📌 Binary Tree Traversal Methods:

🔹 Depth-First Traversal (DFS)

• Inorder (LNR) → Left → Root → Right
• Preorder (NLR) → Root → Left → Right
• Postorder (LRN) → Left → Right → Root

🔹 Breadth-First Traversal (BFS)

• Level Order Traversal → Visit nodes level by level

---

📌 Binary Search Tree (BST) – A Special Binary Tree

A Binary Search Tree (BST) is a binary tree that maintains a sorted order:
✅ Left subtree contains nodes less than the parent.
✅ Right subtree contains nodes greater than the parent.
✅ Enables efficient searching, insertion, and deletion in O(log n) time (if balanced).

---

📌 Applications of Binary Trees:

✅ Expression Trees – Used in compilers & mathematical expressions.
✅ Hierarchical Databases – Organizing data in databases.
✅ Decision Trees – Machine learning & AI-based models.
✅ Binary Heaps – Used in priority queues.
✅ Trie Structures – For fast word search in dictionaries.

Basic Terminology in Tree Data Structure

  Basic Terminology in Tree Data Structure

Understanding trees in data structures requires knowledge of key terms. Here are the most important ones:

📌 Fundamental Terms:

1️⃣ Node – A single element in a tree containing data and pointers to child nodes.
2️⃣ Root – The topmost node in a tree (the starting point).
3️⃣ Edge – A link between two nodes (parent-child relationship).
4️⃣ Parent Node – A node that has child nodes.
5️⃣ Child Node – A node that descends from another node (parent).
6️⃣ Leaf Node – A node with no children.
7️⃣ Sibling Nodes – Nodes that share the same parent.

📌 Structural Terms:

8️⃣ Degree of a Node – The number of children a node has.
9️⃣ Degree of a Tree – The maximum degree of any node in the tree.
🔟 Depth of a Node – The number of edges from the root to that node.
1️⃣1️⃣ Height of a Node – The number of edges from that node to the deepest leaf.
1️⃣2️⃣ Height of a Tree – The height of the root node (max depth of any node).
1️⃣3️⃣ Subtree – A tree formed by a node and its descendants.
1️⃣4️⃣ Level – The distance (in edges) from the root node. The root is at level 0, its children are at level 1, and so on.

📌 Special Types:

1️⃣5️⃣ Binary Tree – A tree where each node has at most two children.
1️⃣6️⃣ Binary Search Tree (BST) – A binary tree where the left child is smaller and the right child is larger than the parent.
1️⃣7️⃣ Balanced Tree – A tree where the height difference between left and right subtrees is minimal.