Complete Binary Tree | DSA in C++ - Software Development PDF Download

Introduction

In the field of data structures and algorithms, binary trees are a fundamental concept. Among them, a complete binary tree is a special type of binary tree that has its nodes filled in a left-to-right order. This article aims to provide a comprehensive understanding of complete binary trees, including their properties, representation, and basic operations, using simple code examples in C++.

What is a Complete Binary Tree?

Properties of Complete Binary Trees

• In a complete binary tree with n nodes, the height of the tree is log₂(n) + 1.
• The number of nodes at the last level or the deepest level is between 1 and 2^(height-1), inclusive.
• A complete binary tree can be uniquely represented using an array.

Representation of Complete Binary Trees

To represent a complete binary tree using an array, we can assign array indices to the nodes of the tree. For a node at index i:

• Its left child is at index 2i + 1.
• Its right child is at index 2i + 2.
• Its parent is at index floor((i - 1) / 2).

Basic Operations on Complete Binary Trees

• Insertion: To insert a node into a complete binary tree, we typically start by inserting the new node in the last available position (leftmost position) of the last level. If the last level is already filled, we move to the next level, always adding new nodes from left to right.
• Deletion: Deletion in a complete binary tree is performed by replacing the node to be deleted with the last node in the tree and then removing the last node. After deletion, if the tree no longer satisfies the complete binary tree property, we perform heapify operations to restore it.

Code Examples and Output

Let's illustrate the concepts with some code examples in C++:

Representation of Complete Binary Tree:

#include <iostream>

using namespace std;

// Complete Binary Tree representation using an array

void displayCompleteBinaryTree(int arr[], int size) {

    for (int i = 0; i < size; i++)

        cout << arr[i] << " ";

}

int main() {

    int arr[] = {1, 2, 3, 4, 5, 6, 7};

    int size = sizeof(arr) / sizeof(arr[0]);    

    cout << "Complete Binary Tree: ";

    displayCompleteBinaryTree(arr, size);  

    return 0;

}

Output:

Complete Binary Tree: 1 2 3 4 5 6 7

Insertion in Complete Binary Tree:

#include <iostream>

using namespace std;

// Complete Binary Tree representation using an array

void insertNode(int arr[], int& size, int value) {

    size++;

    int i = size - 1;

    while (i > 0 && arr[(i - 1) / 2] < value) {

        arr[i] = arr[(i - 1) / 2];

        i = (i - 1) / 2;

    }

    arr[i] = value;

}

int main() {

    int arr[100] = {1, 2, 3, 4, 5, 6, 7};

    int size = 7;

    int value = 8;

    insertNode(arr, size, value);

    cout << "Updated Complete Binary Tree: ";

    displayCompleteBinaryTree(arr, size);

    return 0;

}

Output:

Updated Complete Binary Tree: 1 2 3 4 5 6 7 8

Sample Problems and Solutions

Problem 1: Find the height of a complete binary tree given the number of nodes as input.

The height of a complete binary tree with n nodes can be calculated using the formula log₂(n) + 1.

Problem 2: Delete the root node in a complete binary tree and restore its completeness.

To delete the root node, we replace it with the last node in the tree and then remove the last node. After deletion, we perform heapify operations if necessary to restore the complete binary tree property.

Conclusion

In this article, we have explored complete binary trees in data structures and algorithms. We discussed their properties, representation using arrays, and basic operations like insertion and deletion. By understanding these concepts and practicing with the provided code examples, beginners can enhance their understanding of complete binary trees and apply them in solving various programming problems.