Complete Binary Tree

noun

say it: “kum-PLEET BY-nuh-ree TREE” /kəmˈpliːt ˈbaɪnəri triː/

A binary tree filled level by level, left to right, with no gaps, so it can be stored in an array.

What is a complete binary tree?

A complete binary tree fills every level from left to right before starting the next, with no gaps. That shape lets it live in a plain array: the children of index i are at 2i + 1 and 2i + 2, and its parent at (i - 1) / 2.

In a sentence

  • “A heap is a complete binary tree, so a node's children are always at 2i + 1 and 2i + 2.”

Level: Journeyman · More Data Structures terms at this level

Updated