What is a Complete Binary Tree?

A complete binary tree is a specific type of binary tree structure that is ordered in a particular way, ensuring efficiency in certain applications.

Understanding the Structure: The Complete Binary Tree Defined

Based on standard definitions, a complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. This means that nodes are added level by level, from top to bottom and from left to right within each level.

Let's break down the key aspects:

• Every Level Filled (Except Possibly the Last): All levels of the tree, from the root down to the second-to-last level, must contain the maximum possible number of nodes for that level. A level k (starting from level 0 at the root) can hold up to 2^k nodes.
• Nodes in the Last Level As Far Left As Possible: If the last level is not completely full, the nodes it contains must occupy the leftmost positions available. There should be no gaps between nodes on the last level; if there's a node at a certain position, all positions to its left at that level must also have nodes.

The reference also notes that the last level (level h, where h is the height of the tree) "can have between 1 and 2^h nodes".

Complete vs. Perfect Binary Tree

It's important to distinguish a complete binary tree from a perfect binary tree.

• A perfect binary tree is a binary tree where all levels are completely filled, and all leaf nodes are at the same depth.
• A complete binary tree allows the last level to be partially filled, provided the nodes are left-aligned.

As stated in the reference, "A perfect tree is therefore always complete but a complete tree is not always perfect." A perfect tree is a special case of a complete tree where the last level is also completely filled.

Why are Complete Binary Trees Useful?

Complete binary trees are often used in practical computer science applications because their structure makes them efficient to represent using arrays. Due to the strict level-by-level, left-to-right filling, the relationships between parent and child nodes can be easily calculated using array indices, eliminating the need for explicit pointers in many cases. This forms the basis for data structures like binary heaps.

• Array Representation: In an array, if a node is at index i (starting from index 0 or 1), its left child is at index 2i+1 (or 2i) and its right child is at index 2i+2 (or 2i+1). The parent is at index (i-1)/2 (integer division, or i/2). This formula only works correctly for a tree that is filled like a complete binary tree.
• Efficiency: This contiguous array representation saves memory compared to pointer-based structures and often improves cache performance.

Example Illustration

Consider a binary tree with 7 nodes.

• If it's a perfect binary tree:
  • Level 0: 1 node (root)
  • Level 1: 2 nodes
  • Level 2: 4 nodes
  • Total: 1 + 2 + 4 = 7 nodes. This is also a complete binary tree.
• If it's a complete binary tree with 5 nodes:
  • Level 0: 1 node (root)
  • Level 1: 2 nodes (fully filled)
  • Level 2: 2 nodes (partially filled, but must be the two leftmost positions)
  • This tree is complete. If the two nodes at Level 2 were not the leftmost ones (e.g., there was a gap), it would not be complete.

Understanding the properties of complete binary trees is fundamental for studying certain algorithms and data structures that rely on this specific arrangement.