Which of the following are true for a complete binary tree?
A. It has always odd number of vertices.
B. With i internal vertices, it has i+1 leaves.
C. With l leaves, it has 2l-1 vertices.
D. With 2 n-1 vertices, it has n leaves.
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: D. A, B, C, D
Explanation
Here 'complete' means every internal node has two children. Then leaves = internal + 1, total nodes = 2l − 1 (always odd), and 2n − 1 nodes means n leaves. All four statements hold.
More Data Structures and Algorithms questions
- Which of the following is TRUE?
- 2-3-4 trees are B - trees of order 4. They are isometric of trees.
- Match List I with List II. List I: A. Parallel FFT, B. Iterative FFT, C. Evaluation of a polynomial at n points by Horner's method, D. Prod…
- Let f(n) and g(n) be asymptotically positive functions. Statement I: f(n) ≥ 1 and f(n) = O(g(n)) ⇒ g(n) = Ω(f(n)). Statement II: f(n) = O(g…
- A. If some NP-complete problem P is in 𝒫, then 𝒫 = 𝒩𝒫. B. TSP is in 𝒩𝒫. C. SAT is in 𝒩𝒫. D. The Hamiltonian circuit problem is not NP-compl…
- Suppose a circular queue of capacity n-1 elements is implemented with an array of n elements. Assume that the insertion and deletion operat…