Past exam question: 2066 Jestha (Back), Q10(a)
Open in the Padhaiko appQuestion
Write short notes on: a) Almost Complete Binary Tree
Solution
Almost Complete Binary Tree: An almost complete binary tree (also called a complete binary tree in heap literature) of height satisfies two rules:
- Every level from to is completely filled with nodes ( nodes at level ).
- On the deepest level , all existing leaf nodes are packed consecutively to the left without any gaps.
- Key Property: It maps compactly onto a 0-indexed (or 1-indexed) array with zero wasted holes (left child at , right child at ), making it the structural foundation of binary heaps and heap sort.
Answer:
An almost complete binary tree has all levels completely full and level filled strictly from left to right, enabling gap-free array storage for binary heaps.