complete binary tree
A binary tree in which every level is full except possibly the last, which is filled from the left with no gaps.
In more detail
The no-gaps shape is what lets a heap live in a plain array: position alone tells you each node's parent and children. Its height is always floor(log2 n). A perfect binary tree is the special case where the last level is full too, holding 2^(h+1) - 1 nodes.
Related terms
- binary heap — A complete binary tree stored in an array in which every parent is ordered before its children, so the smallest (or largest) item is always at the root.
- binary tree — A tree in which every node has at most two children, called the left child and the right child.
Taught in
- Binary Trees And Their Traversals — Algorithms & Data Structures for Working Engineers
- Binary Search Trees: Search, Insert And Delete — Algorithms & Data Structures for Working Engineers
- AVL Trees: Rotations That Keep The Guarantee — Algorithms & Data Structures for Working Engineers
- Heaps And Priority Queues — Algorithms & Data Structures for Working Engineers