What is the minimum number of nodes in a nearly complete binary tree with height 4? (In a tree the height of root is 1, and a binary tree with height h is called nearly complete if the tree is complete at level d for d = 1, 2, ..., h-1, and the leaves in the last level are all in the leftmost positions).

Đáp án đúng: "8". Gốc tính là mức 1 nên cây cao 4 có bốn mức; định nghĩa đòi các mức 1, 2, 3 phải đầy, cho 1 + 2 + 4 = 7 nút, và mức 4 phải có ít nhất một lá, nếu không cây chỉ cao 3. Vậy số nút ít nhất là 7 + 1 = 8, với lá duy nhất của mức cuối nằm sát bên trái. Con số "7" là tổng của ba mức đầy nhưng mức 4 rỗng, tức cây cao 3 chứ không phải 4. Con số "9" ứng với hai lá ở mức cuối, vẫn hợp lệ nhưng chưa ít nhất vì bớt một lá cây vẫn còn cao 4. Con số "6" không đủ cho ba mức đầu đầy, mức 3 sẽ thiếu nút nên vi phạm điều kiện đầy ở mọi mức trước mức cuối.