Complete Binary Tree

Introduction

Complete binary trees are a fundamental concept in computer science, particularly in the field of data structures. These trees are special because they ensure a balanced distribution of nodes, making operations like search, insert, and delete more efficient compared to unbalanced trees. This article will guide you through the complexities of complete binary trees, covering everything from basic definitions to their applications.

What is a Complete Binary Tree?

A complete binary tree is a special type of binary tree where all the levels are completely filled except possibly for the last level, which is filled from the left towards the right. This structure ensures that the tree remains as compact as possible, minimizing the number of levels and thereby optimizing operations like search, insertion, and deletion.

To put it simply, imagine organizing a group of people into a queue that fills up row by row, starting from the front. A complete binary tree follows a similar approach with its nodes. Each level of the tree is filled with nodes before moving on to the next level, and this process continues until there's no space left or no nodes left to add.

This characteristic makes complete binary trees ideal for data structures like heaps, which are used in algorithms such as heap sort or for implementing priority queues. The compact nature of complete binary trees ensures that the maximum height of the tree is kept to a minimum, thereby reducing the time it takes to traverse from the root of the tree to the deepest node.

In the context of computer science, this efficiency translates to faster execution times for certain operations, making complete binary trees a go-to choice for various applications.

Terminologies of Complete Binary Tree

When diving into complete binary trees, it's essential to get familiar with some basic terms to better understand how these trees work. Here are a few key terms:

1. Node

This is the basic unit of a binary tree. You can think of it as a box that holds data and has links to other boxes (or nodes). Each node in a binary tree can have up to two children.

2. Root

The root is the very top node of the tree. It's where everything starts. There's only one root in a tree, and it's the only node without a parent.

3. Level

The level of a node is determined by how many connections (or edges) it is away from the root. The root is at level 0, its children are at level 1, and so on.

4. Leaf

A leaf is a node that doesn't have any children. It's like the end of a branch in a real tree.

5. Parent and Child

In a binary tree, each node (except the root) has one parent, and each parent can have up to two children. The parent is the node directly above, and the children are the nodes directly below.

6. Depth

The depth of a tree is the number of levels it has. It's like measuring how tall the tree is, but instead of feet or meters, we use levels.

7. Balanced

A balanced tree is one where no leaf is much farther away from the root than any other leaf. This doesn't necessarily mean that all leaves are at the same level, but the levels shouldn't vary too much.

Properties of Complete Binary Tree

Complete binary trees have unique characteristics that set them apart from other types of binary trees. Understanding these properties can help you recognize a complete binary tree and appreciate why they are used in certain applications. Here are the key properties:

Level-by-Level Filling

In a complete binary tree, nodes are added level by level, starting from the left. This means that each level must be completely filled before moving on to the next one, except possibly for the last level.

Last Level Filling

The last level of a complete binary tree can be partially filled, but the filling must occur from left to right without any gaps in between. This ensures the tree remains as compact as possible.

Minimum Height

Due to their level-by-level filling, complete binary trees have the minimum possible height for the number of nodes they contain. The height of a complete binary tree with n nodes is [log₂(n+1)]-1 where ⌈x⌉ denotes the smallest integer greater than or equal to x.

Maximum Nodes at Any Level

For any given level i, the maximum number of nodes it can have is 2^i.This is because each node can have at most two children, doubling the number of nodes as you move down each level.

Total Node Count

A complete binary tree with a height of h can have a minimum of 2^h nodes (when the last level has just one node) and a maximum of 2^(h+1) −1 nodes (when all levels are fully filled).

Efficient Representation

Complete binary trees can be efficiently represented using arrays. The parent-child relationships can be mapped using indices, where the children of the node at index i are at indices2i+1 (for the left child) and 2i+2 (for the right child).

These properties make complete binary trees an ideal choice for implementing data structures like heaps, which require quick access to the 'highest priority' item and need to maintain a balanced shape to ensure efficient operations.

How a Complete Binary Tree is Created?

Creating a complete binary tree involves adding nodes in such a way that each level of the tree is fully filled before moving on to the next level, and any new nodes are added from left to right. This process ensures the tree remains balanced and compact, optimizing the performance of many tree-based operations. Here's a step-by-step guide to creating a complete binary tree:

Step 1: Start with the Root

Begin by creating the root node. This will be the only node in the tree at the start and it sits at level 0.

Step 2: Add Nodes Level by Level

Proceed to add nodes to the tree one level at a time. Ensure that each level is completely filled before moving on to the next level.

    A
   / \
  B   C

Step 3: Left to Right Filling

When adding nodes to a level that is not yet completely filled, add them from left to right. This ensures that there are no gaps on the left side of any level.

    A
   / \
  B   C
 / \
D   E

Step 4: Use a Queue for Insertion

A practical way to implement the creation of a complete binary tree is by using a queue. Start by enqueuing the root node. Then, while there are nodes in the queue, perform the following steps:

Queue: [A]

    A
   / \
  B   C
 / \
D   E

Step 5: Dequeue a node from the front of the queue.

If the left child of this node doesn't exist, create a new node and set it as the left child. Enqueue this new node.

If the left child exists but the right child does not, create a new node and set it as the right child. Enqueue this new node.

1. Dequeue A
Queue: []

    A
   / \
  B   C
 / \
D   E

2. A's left child exists, check right child
Queue: [B, C]

    A
   / \
  B   C
 / \
D   E
  \
   F (added)

Step 6: Repeat Until Complete

Continue this process until the tree has the desired number of nodes or until the last level is filled from left to right as needed.

Final Queue: []

    A
   / \
  B   C
 / \   \
D   E   F

(Next node would be added to C's right, following the same queue-based insertion logic)

Example of Complete Binary Tree

Here's an example of how you might implement this in code, using a simple Node class and a function to add nodes:

C++
Java
Python
JavaScript
C#

C++

#include <iostream>
#include <queue>
using namespace std;

class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node(int key) {
        val = key;
        left = right = nullptr;
    }
};

void insert(Node* root, int key) {
    if (!root) {
        root = new Node(key);
        return;
    }

    queue<Node*> q;
    q.push(root);

    while (!q.empty()) {
        Node* temp = q.front();
        q.pop();

        if (!temp->left) {
            temp->left = new Node(key);
            break;
        } else {
            q.push(temp->left);
        }

        if (!temp->right) {
            temp->right = new Node(key);
            break;
        } else {
            q.push(temp->right);
        }
    }
}

// Example usage
int main() {
    Node* root = new Node(1);
    insert(root, 2);
    insert(root, 3);
    insert(root, 4);
    insert(root, 5);

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Java

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

class Node {
    int val;
    Node left, right;

    Node(int key) {
        val = key;
        left = right = null;
    }
}

public class BinaryTree {
    public static void insert(Node root, int key) {
        if (root == null) {
            root = new Node(key);
            return;
        }

        Queue<Node> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            Node temp = queue.poll();

            if (temp.left == null) {
                temp.left = new Node(key);
                break;
            } else {
                queue.add(temp.left);
            }

            if (temp.right == null) {
                temp.right = new Node(key);
                break;
            } else {
                queue.add(temp.right);
            }
        }
    }

    // Example usage
    public static void main(String[] args) {
        Node root = new Node(1);
        insert(root, 2);
        insert(root, 3);
        insert(root, 4);
        insert(root, 5);
    }
}

You can also try this code with Online Java Compiler

Run Code

Python

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

def insert(root, key):
    if root is None:
        return Node(key)

    queue = []
    queue.append(root)

    while queue:
        temp = queue.pop(0)

        if not temp.left:
            temp.left = Node(key)
            break
        else:
            queue.append(temp.left)

        if not temp.right:
            temp.right = Node(key)
            break
        else:
            queue.append(temp.right)

# Example usage
root = Node(1)
insert(root, 2)
insert(root, 3)
insert(root, 4)
insert(root, 5)

You can also try this code with Online Python Compiler

Run Code

JavaScript

class Node {
    constructor(key) {
        this.val = key;
        this.left = null;
        this.right = null;
    }
}

function insert(root, key) {
    if (root === null) {
        root = new Node(key);
        return;
    }

    let queue = [];
    queue.push(root);

    while (queue.length > 0) {
        let temp = queue.shift();

        if (temp.left === null) {
            temp.left = new Node(key);
            break;
        } else {
            queue.push(temp.left);
        }

        if (temp.right === null) {
            temp.right = new Node(key);
            break;
        } else {
            queue.push(temp.right);
        }
    }
}

// Example usage
let root = new Node(1);
insert(root, 2);
insert(root, 3);
insert(root, 4);
insert(root, 5);

You can also try this code with Online Javascript Compiler

Run Code

C#

using System;
using System.Collections.Generic;

class Node {
    public int val;
    public Node left, right;

    public Node(int key) {
        val = key;
        left = right = null;
    }
}

class BinaryTree {
    public static void Insert(Node root, int key) {
        if (root == null) {
            root = new Node(key);
            return;
        }

        Queue<Node> queue = new Queue<Node>();
        queue.Enqueue(root);

        while (queue.Count > 0) {
            Node temp = queue.Dequeue();

            if (temp.left == null) {
                temp.left = new Node(key);
                break;
            } else {
                queue.Enqueue(temp.left);
            }

            if (temp.right == null) {
                temp.right = new Node(key);
                break;
            } else {
                queue.Enqueue(temp.right);
            }
        }
    }

    // Example usage
    public static void Main() {
        Node root = new Node(1);
        Insert(root, 2);
        Insert(root, 3);
        Insert(root, 4);
        Insert(root, 5);
    }
}

This process results in a complete binary tree that's balanced and efficient for various operations.

Application of the Complete Binary Tree

Complete binary trees play a crucial role in computer science and have various practical applications. Understanding these applications can help you grasp why complete binary trees are so valuable. Here are seven key applications:

Binary Heaps

One of the most common uses of complete binary trees is in implementing binary heaps. Binary heaps are a type of data structure that can efficiently implement priority queues. They rely on the properties of complete binary trees to ensure that operations like insertion, deletion, and finding the minimum or maximum elements can be done quickly.

Heap Sort

Leveraging the structure of binary heaps, complete binary trees are also used in heap sort, an efficient sorting algorithm. Heap sort organizes elements using the properties of complete binary trees, allowing for fast sorting of data.

Binary Search Trees (BSTs)

While not all BSTs are complete binary trees, ensuring a BST is complete can improve efficiency. A complete BST guarantees faster search, insertion, and deletion operations due to its balanced nature.

Database Indexing

Some database indexing methods use complete binary trees to speed up data retrieval. The balanced nature of complete binary trees makes them ideal for indexing large datasets.

Networking

In networking, complete binary trees can structure network routing and broadcasting algorithms. Their structure helps optimize the path for data packets, reducing latency and improving speed.

Huffman Coding Trees

Huffman coding, used in data compression, often uses complete binary trees to create efficient prefix codes. This application takes advantage of the tree's structure to minimize the total weighted path length of the codes.

Decision Trees

In machine learning and data mining, complete binary trees are used in decision tree algorithms for classification and regression. Their structure helps in breaking down a dataset into smaller subsets while at the same time developing an associated decision tree.

Perfect Binary Tree vs Complete Binary Tree

Feature	Perfect Binary Tree	Complete Binary Tree
Definition	A binary tree in which all interior nodes have two children and all leaves are at the same level.	A binary tree in which all levels are fully filled except possibly for the last level, which is filled from left to right.
Node Placement	Every level, including the last level, must be completely filled.	All levels are filled except possibly the last, which is filled left to right as needed.
Height and Nodes Relationship	The number of nodes is exactly 2^(ℎ+1)−1 where 'h' is the height of the tree.	The number of nodes ranges between 2^{h and} 2^(ℎ+1)−1 inclusive.
Last Level Nodes	The last level is completely filled with leaves.	The last level may not be completely filled, but if not, all nodes are as far left as possible.
Structural Property	A perfect binary tree is automatically a complete binary tree, but with the added condition that all leaf nodes must be at the same depth.	A complete binary tree might not be perfect if the last level is not completely filled.
Applications	Used in scenarios where a full and complete tree structure is required, such as certain tree-based algorithms that rely on a full tree structure for efficiency.	Often used in priority queues implemented as binary heaps, where the need to maintain a full tree for every operation is not as critical, allowing for more flexibility in node placement.

Full Binary Tree vs Complete Binary Tree

Feature	Full Binary Tree	Complete Binary Tree
Node Characteristics	Every node has either 0 or 2 children. No node can have only one child.	A node can have 0, 1, or 2 children, with nodes filled from left to right at the last level.
Level Completion	Not all levels need to be fully occupied.	All levels are filled except possibly the last, which is filled from left to right.
Tree Shape	Can have gaps in levels as long as each node has two or no children.	Forms a compact shape with no gaps in levels except possibly the last.
Height	The height can vary widely depending on the distribution of nodes.	Typically has the minimum possible height for the given number of nodes.
Last Level	Does not require the last level to be filled or partially filled in any specific order.	The last level may not be fully filled but must have all nodes as far left as possible.
Applications	Often used in decision trees, expression trees, and certain algorithm implementations that require strict binary node relationships.	Commonly used in binary heaps and priority queues where the compact structure optimizes storage and retrieval efficiency.

Learn about Full Binary Tree vs Complete Binary Tree in detail

Frequently Asked Questions

Can a complete binary tree be unbalanced?

While a complete binary tree is generally more balanced than arbitrary binary trees, it can be slightly unbalanced, especially if the last level is not fully filled. However, the degree of imbalance is minimal compared to other tree structures.

What is strictly binary tree and complete binary tree?

A strictly binary tree, also known as a full binary tree, is a tree in which every node has either 0 or 2 children. This means that no node has only one child; each node is either a leaf or has exactly two children. A complete binary tree is a binary tree in which all levels are completely filled except possibly the last level. In the last level, all nodes are as far left as possible, ensuring there are no gaps in the node arrangement.

How do you determine if a binary tree is complete?

To determine if a binary tree is complete, check that all levels except possibly the last are fully filled, and nodes at the last level are as far left as possible. This can be verified using level-order traversal to ensure that no node is missing in between.

Why are complete binary trees preferred for binary heaps?

Complete binary trees are preferred for binary heaps because they ensure the heap is always a compact tree with minimal height, which optimizes the performance of heap operations like insert, delete, and find-min/find-max.

Conclusion

In this article, we've learned the concept of complete binary trees, a fundamental structure in computer science known for its balanced and compact nature. Starting with a basic definition, we looked into essential terminology, properties that distinguish complete binary trees, and how they compare to perfect and full binary trees. We also covered the creation process, which ensures a balanced structure by adding nodes level by level, from left to right.

You can refer to our guided paths on Code360. You can check our course to learn more about DSA, DBMS, Competitive Programming, Python, Java, JavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.

Introduction

What is a Complete Binary Tree?

Terminologies of Complete Binary Tree

1. Node

2. Root

3. Level

4. Leaf

5. Parent and Child

6. Depth

7. Balanced

Properties of Complete Binary Tree

Level-by-Level Filling

Last Level Filling

Minimum Height

Maximum Nodes at Any Level

Total Node Count

Efficient Representation

How a Complete Binary Tree is Created?

Step 1: Start with the Root

Step 2: Add Nodes Level by Level

Step 3: Left to Right Filling

Step 4: Use a Queue for Insertion

Step 5: Dequeue a node from the front of the queue.

Step 6: Repeat Until Complete

Example of Complete Binary Tree

C++

Java

Python

JavaScript

C#

Application of the Complete Binary Tree

Binary Heaps

Heap Sort

Binary Search Trees (BSTs)

Database Indexing

Networking

Huffman Coding Trees

Decision Trees

Perfect Binary Tree vs Complete Binary Tree

Full Binary Tree vs Complete Binary Tree

Frequently Asked Questions

Can a complete binary tree be unbalanced?

​​What is strictly binary tree and complete binary tree?

How do you determine if a binary tree is complete?

Why are complete binary trees preferred for binary heaps?

Conclusion

What is strictly binary tree and complete binary tree?