Complete Binary Trees

---

A Complete Binary Tree is a binary tree in which all the levels of the tree are fully filled except possibly for the last level. The last level is filled from left to right, meaning all the nodes at the last level are as left as possible. This tree structure is widely used in implementing heap data structures and binary search trees.

---

What is a Complete Binary Tree?

A Complete Binary Tree is defined as a binary tree in which:

1. Every level, except possibly the last, is completely filled.
2. All nodes are as far left as possible in the last level.

Key Characteristics of a Complete Binary Tree:

• Height: The height of a complete binary tree is $h=\lfloor {\log }_2(n)\rfloor$, where $n$ is the number of nodes in the tree.
• Nodes in Last Level: Nodes at the last level are filled from left to right.
• Balanced: While it may not be perfectly balanced, a complete binary tree is well-balanced as the nodes are filled level by level, keeping the structure compact.

A complete binary tree is very useful in heap data structures (like binary heaps) due to its level-wise compact structure.

---

Properties of Complete Binary Trees

1. Fullness: All levels are filled completely except possibly the last one. This means the tree remains "full" as much as possible.
2. Node Count: A complete binary tree of height $h$ contains $n$ nodes such that: $$2^h-1\le n\le 2^{h+1}-1$$ where $h$ is the height of the tree.
3. Shape: The tree is always left-leaning at the last level.
4. Depth and Height: A complete binary tree with $n$ nodes has a height of $\lfloor {\log }_2(n)\rfloor$.
5. Efficient for Storing Data: The compact nature of a complete binary tree makes it efficient for storing data in arrays.

Example of a Complete Binary Tree

Here is an example of a complete binary tree:

        1
       / \
      2   3
     / \  / 
    4  5 6

In this tree:

• The first two levels are completely filled.
• The third level has nodes 4, 5, and 6, but node 7 is missing, so the tree is complete but not perfect.

---

Difference Between Perfect and Complete Binary Tree

• Perfect Binary Tree:

  • All internal nodes have exactly two children.
  • All leaf nodes are at the same level.
  • All levels are completely filled.
  • Example: A tree with 7 nodes.

• Complete Binary Tree:

  • All levels except possibly the last are completely filled.
  • The last level is filled from left to right.
  • The leaf nodes are not necessarily at the same level, but they are as left as possible.
  • Example: A tree with 6 nodes.

---

Operations on Complete Binary Trees

1. Insertion in a Complete Binary Tree

Insertion in a complete binary tree follows a level-order approach. The new node is added at the leftmost available position on the last level, which ensures that the tree maintains its "complete" structure.

• Heap Property: In a min-heap or max-heap, insertion must also maintain the heap property. The node is first inserted at the leftmost available position, and then the heap property is restored by bubbling up the new node.

2. Traversing a Complete Binary Tree

Traversing a binary tree is the process of visiting all its nodes. The common types of tree traversal are:

• Preorder Traversal: Visit the root, traverse the left subtree, then traverse the right subtree.
• Inorder Traversal: Traverse the left subtree, visit the root, then traverse the right subtree.
• Postorder Traversal: Traverse the left subtree, traverse the right subtree, then visit the root.
• Level-order Traversal: Traverse the tree level by level, from the root to the deepest level.

3. Deletion in a Complete Binary Tree

Deletion in a complete binary tree typically removes the deepest node (the rightmost node) to maintain the completeness of the tree. In some cases, when deleting the root, the tree might be restructured, and the deepest node will replace the root, followed by a heapification process.

---

Code Example: Complete Binary Tree in Python

Below is a Python implementation of a Complete Binary Tree. It supports insertion, level-order traversal, and both preorder and inorder traversal.

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.value = key

class CompleteBinaryTree:
    def __init__(self):
        self.root = None
        self.size = 0  # Keeps track of the number of nodes in the tree
    
    # Level order insertion for a complete binary tree
    def insert(self, root, key):
        if root is None:
            return Node(key)
        
        queue = [root]
        while queue:
            temp = queue.pop(0)
            
            # Insert the node in the left child if it's empty
            if temp.left is None:
                temp.left = Node(key)
                return root
            else:
                queue.append(temp.left)
            
            # Insert the node in the right child if it's empty
            if temp.right is None:
                temp.right = Node(key)
                return root
            else:
                queue.append(temp.right)
    
    # Level order traversal (breadth-first)
    def level_order_traversal(self, root):
        if not root:
            return
        queue = [root]
        while queue:
            temp = queue.pop(0)
            print(temp.value, end=" ")
            if temp.left:
                queue.append(temp.left)
            if temp.right:
                queue.append(temp.right)
    
    # Preorder traversal (root-left-right)
    def preorder_traversal(self, root):
        if root:
            print(root.value, end=" ")  # Visit root
            self.preorder_traversal(root.left)  # Visit left subtree
            self.preorder_traversal(root.right)  # Visit right subtree
    
    # Inorder traversal (left-root-right)
    def inorder_traversal(self, root):
        if root:
            self.inorder_traversal(root.left)  # Visit left subtree
            print(root.value, end=" ")  # Visit root
            self.inorder_traversal(root.right)  # Visit right subtree

# Example Usage
cbt = CompleteBinaryTree()
cbt.root = cbt.insert(cbt.root, 1)
cbt.insert(cbt.root, 2)
cbt.insert(cbt.root, 3)
cbt.insert(cbt.root, 4)
cbt.insert(cbt.root, 5)
cbt.insert(cbt.root, 6)

print("Level Order Traversal of Complete Binary Tree:")
cbt.level_order_traversal(cbt.root)

print("\nPreorder Traversal of Complete Binary Tree:")
cbt.preorder_traversal(cbt.root)

print("\nInorder Traversal of Complete Binary Tree:")
cbt.inorder_traversal(cbt.root)

Output:

Level Order Traversal of Complete Binary Tree:
1 2 3 4 5 6 

Preorder Traversal of Complete Binary Tree:
1 2 4 5 3 6 

Inorder Traversal of Complete Binary Tree:
4 2 5 1 3 6

---

Applications of Complete Binary Trees

1. Heap Data Structures: Complete binary trees are commonly used in binary heaps to implement priority queues. In heaps, insertion and deletion operations maintain the complete binary tree structure, ensuring efficient retrieval of the maximum or minimum element.

2. Balanced Search Trees: Although complete binary trees themselves are not always used in search trees, they serve as a foundation for AVL trees and Red-Black trees, which are balanced and maintain optimal search times.

3. Binary Indexed Trees (Fenwick Trees): Complete binary trees are used in Fenwick trees for efficient range sum queries and updates.

4. Efficient Memory Storage: The structure of a complete binary tree is ideal for storing data in arrays, as it allows for efficient traversal and indexing.

---

---