What Is Complete Binary Tree in Data Structure With Example?

//

Larry Thompson

A complete binary tree is a special type of binary tree in data structure where all levels, except possibly the last, are completely filled, and all nodes are as far left as possible. In other words, it is a binary tree in which each level is completely filled, except for the last level which is filled from left to right.

Properties of a Complete Binary Tree:

  • Shape Property: A complete binary tree of height h has 2h-1 nodes.
  • Height Property: The height of a complete binary tree with n nodes is ⌊log2n⌋. (⌊x⌋ denotes the floor function)
  • Indexing Property: For any node at index i (1-based indexing) in a complete binary tree, its children will be at indexes 2i and 2i+1.

Example:

To better understand a complete binary tree, let’s consider an example.

Input:

      A
     / \
    B   C
   / \   \
  D   E   F

In this example, we have a complete binary tree with six nodes. The levels are filled from left to right until the last level. All nodes are as far left as possible.

Explanation:

The root node ‘A’ is at level 0 and has two children ‘B’ and ‘C’ at levels 1. Node ‘B’ has its children ‘D’ and ‘E’, both at level 2. Node ‘C’ has its only child ‘F’ at level 2.

Visually, the complete binary tree looks like this:

      A
     / \
    B   C
   / \   \
  D   E   F

Here, the tree is complete because all levels are completely filled except for the last level, which is filled from left to right.

Conclusion:

A complete binary tree is an important concept in data structures. It ensures efficient storage and retrieval of data. Understanding its properties and examples will help in implementing algorithms and solving problems efficiently.

Discord Server - Web Server - Private Server - DNS Server - Object-Oriented Programming - Scripting - Data Types - Data Structures

Privacy Policy