Complete Binary Trees

Introduction

Complete binary trees are fascinating structures in the realm of data structures and algorithms. They possess unique properties and offer efficient representation, making them valuable in various applications. In this article, we will explore complete binary trees comprehensively, understanding their definition, properties, creation, algorithms, and practical implementations.

A complete binary tree is a binary tree in which all levels, except possibly the last one, are completely filled and all nodes are left-justified. It is a balanced structure that ensures efficient storage and retrieval of data. Complete binary trees have crucial applications in areas like heap data structures, binary heaps, and binary search trees.

What Is a Complete Binary Tree?

A complete binary tree can be visualized as a binary tree where all levels, except the last one, are filled with nodes. In the last level, nodes are filled from left to right without any gaps. This unique property ensures that the tree is perfectly balanced. Let's consider an example to understand this better.

Example:

In this example, the tree is a complete binary tree, as all levels are filled except for the last level, where the nodes are filled from left to right.

Some Terminology of Complete Binary Trees

Before we delve deeper into complete binary trees, let's familiarize ourselves with some essential terminology:

1. Parent Node: A node that has one or more child nodes below it.
2. Child Nodes: Nodes that are directly connected to a parent node.
3. Left Child: The node that appears to the left of a parent node.
4. Right Child: The node that appears to the right of a parent node.
5. Sibling Nodes: Nodes that share the same parent node.
6. Leaf Nodes: Nodes that do not have any child nodes.
7. Internal Nodes: Nodes that have at least one child node.

Properties of Complete Binary Trees

Complete binary trees possess several key properties that distinguish them from other tree structures:

1. Balance: Complete binary trees are perfectly balanced, except for the last level. This balance ensures optimal storage and efficient operations.
2. Efficient Representation: Due to their balanced nature, complete binary trees can be efficiently represented using arrays or lists.
3. Efficient Search: The balance of a complete binary tree ensures efficient search operations, making it suitable for various algorithms.
4. Heap Implementation: Complete binary trees are widely used in heap data structures, enabling efficient heap operations like insertion, deletion, and extraction of minimum or maximum values.
5. Sorting Algorithms: Complete binary trees play a vital role in sorting algorithms like Heap Sort, where they serve as the underlying structure for heap data structures.

How is a Complete Binary Tree Created?

To create a complete binary tree, a specific algorithm is followed. Let's explore the steps involved in creating a complete binary tree.

Algorithm:

• Create an empty queue to store the nodes.
• Initialize the root node and add it to the queue.
• While the queue is not empty, perform the following steps:
• Remove the first node from the queue.
• Prompt the user to enter the left child of the current node and add it to the queue.
• Prompt the user to enter the right child of the current node and add it to the queue.

Intuition Behind the Algorithm:

The algorithm ensures that the nodes are added to the tree level by level from left to right, maintaining the complete binary tree structure. By using a queue, we can process the nodes in a First-In-First-Out (FIFO) manner, ensuring the correct order of insertion.

Complete binary tree example:

1. Consider the following example to better understand the creation of a complete binary tree:

2. After adding the left child (2) and right child (3) of the root node (1), the tree becomes:

This makes an almost complete binary tree.

3. Continuing the process, we add the left child (4) and right child (5) of node 2 and the left child (6) of node 3:

By following the algorithm, we successfully create a complete binary tree.

Checking If a Binary Tree is a Complete Binary Tree

To determine if a binary tree is a complete binary tree, we can use various methods. Let's explore two popular approaches in Java and C++.

1. Check if a Binary Tree is a Complete Binary Tree in Java:

import java.util.LinkedList;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

public class CompleteBinaryTreeChecker {
    public static void main(String[] args) {
        // Create a sample binary tree
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);

        // Check if the binary tree is complete
        boolean isComplete = isCompleteBinaryTree(root);

        // Print the result
        System.out.println("Is the binary tree complete? " + isComplete);
    }

    public static boolean isCompleteBinaryTree(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean isLastLevel = false;

        while (!queue.isEmpty()) {
            TreeNode current = queue.poll();
            if (current == null) {
                isLastLevel = true;
            } else {
                if (isLastLevel) {
                    return false;
                }
                queue.offer(current.left);
                queue.offer(current.right);
            }
        }
        return true;
    }
}

2. Check if a Binary Tree is a Complete Binary Tree in C++

#include <queue>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val) : val(val), left(nullptr), right(nullptr) {}
};

bool isCompleteBinaryTree(TreeNode* root) {
    std::queue<TreeNode*> queue;
    queue.push(root);
    bool isLastLevel = false;

    while (!queue.empty()) {
        TreeNode* current = queue.front();
        queue.pop();
        if (current == nullptr) {
            isLastLevel = true;
        } else {
            if (isLastLevel) {
                return false;
            }
            queue.push(current->left);
            queue.push(current->right);
        }
    }
    return true;
}

int main() {
    // Create a sample binary tree
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);

    // Check if the binary tree is complete
    bool isComplete = isCompleteBinaryTree(root);

    // Print the result
    std::cout << "Is the binary tree complete? " << (isComplete ? "true" : "false") << std::endl;

    return 0;
}

Other Methods to Check if a Binary Tree is a Complete Binary Tree or Not.

Apart from the iterative level order traversal method shown above, there are additional ways to check if a binary tree is a complete binary tree. Some popular methods include depth-first search (DFS) and recursive approaches.

1. Level Order Traversal (BFS)

Level order traversal, also known as Breadth-First Search (BFS), is a widely used technique to traverse and process binary trees. It follows the approach of processing the nodes level by level, from left to right.

• Implementation of Algorithm in C++:

• Implementation of Algorithm in Java:

Array Representation of a Complete Binary Tree

Complete binary trees can be efficiently represented using arrays, providing compact storage and easy access to elements. The array representation allows us to map the complete binary tree structure onto an array.

• Implementation of Algorithm in C++ (method):

• Implementation of Algorithm in Java (code example):

class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;

    TreeNode(int data) {
        this.data = data;
    }
}

public class Main {
    public static void main(String[] args) {
        // Create a complete binary tree
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);

        // Create an array to store the elements of the binary tree
        int[] arr = new int[7];

        // Convert the complete binary tree to an array
        completeBinaryTreeToArray(root, arr, 0);

        // Print the array elements
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    public static void completeBinaryTreeToArray(TreeNode root, int[] arr, int index) {
        if (root == null) {
            return;
        }

        arr[index] = root.data;
        completeBinaryTreeToArray(root.left, arr, 2 * index + 1);
        completeBinaryTreeToArray(root.right, arr, 2 * index + 2);
    }
}

Output:

Complete Binary Tree vs Full binary Tree

While complete binary trees and full binary trees share some similarities, they also have some distinct differences:

• Full Binary Tree:

A full binary tree is a binary tree in which every node has either 0 or 2 children. In other words, every node is either a leaf node or an internal node with two child nodes.

• Complete Binary Tree:

A complete binary tree, as discussed earlier, is a binary tree where all levels, except possibly the last one, are completely filled. It is left-justified, meaning that nodes are filled from left to right in the last level.

Complete Binary Tree Applications

Complete binary trees find applications in various domains, including:

• Heap Data Structures: Complete binary trees serve as the underlying structure for heap data structures, enabling efficient heap operations like insertion, deletion, and extraction of minimum or maximum values.
• Binary Heaps: Binary heaps, commonly used for priority queues, use complete binary trees to maintain their properties and perform efficient operations.
• Binary Search Trees: Complete binary trees are also utilized in binary search trees, facilitating efficient searching, insertion, and deletion operations.

Complete Binary Tree in Data Structure

A complete binary tree is a fundamental concept in data structures. It is a type of binary tree that has unique properties and offers an efficient representation for storing and retrieving data. In a complete binary tree, all levels, except possibly the last one, are completely filled, and the nodes are left-justified. This balance ensures optimal storage and enables efficient operations.

The complete binary tree structure is often used in various applications, including heap data structures, binary heaps, and binary search trees. Its balanced nature allows for efficient searching, insertion, and deletion operations. Complete binary trees can be represented using arrays or lists, providing compact storage and easy access to elements.

A Strictly Binary Tree

A strictly binary tree is a specific type of binary tree that imposes a restriction on the number of children each node can have. In a strictly binary tree, every node can have either 0 or 2 children, but not 1 child. This means that each internal node in a strictly binary tree must always have exactly two children.

This restriction creates a balanced and predictable structure within the tree. It ensures that every level is fully occupied, resulting in a more uniform distribution of nodes and a symmetrical appearance.

Conclusion

Complete binary trees are considered remarkable structures that offer balance, efficient representation, and practical applications. By understanding their intricacies, properties, creation, and algorithms, we can leverage their benefits to the fullest in various domains. Whether in heap data structures or sorting algorithms, complete binary trees continue to play a crucial role in computer science and programming.

FAQs

1. How do you determine if a binary tree is a complete binary tree?

Determining whether a binary tree is complete involves checking if the tree satisfies the properties of a complete binary tree. This can be done using various methods such as level order traversal (BFS), recursive approaches, or depth-first search (DFS). By analyzing the structure and properties of the tree, you can determine if it meets the criteria of a complete binary tree.

2. How is a complete binary tree represented using an array?

A complete binary tree can be efficiently represented using an array. The array representation follows a specific mapping, where the root node is stored at index 0, and for any node at index 'i', its left child is located at index '2i + 1' and its right child at index '2i + 2'.

3. How can a complete binary tree be created from given data?

A complete binary tree can be created by using three traversals as follows:

• Inorder traversal, where the nodes are visited in the following order: left subtree, current node, right subtree.
• Preorder traversal, where the nodes are visited in the following order: current node, left subtree, right subtree.
• The postorder traversal, here the nodes are visited in the following order: left subtree, right subtree, current node.