A binary search tree in which every non-leaf node has non-empty left and right…
2018
A binary search tree in which every non-leaf node has non-empty left and right subtrees is called a strictly binary tree. Such a tree with 19 leaves :
- A.
cannot have more than 37 nodes
- B.
has exactly 37 nodes
- C.
has exactly 35 nodes
- D.
cannot have more than 35 nodes
Attempted by 386 students.
Show answer & explanation
Correct answer: B
Definition: A strictly binary tree (also called a full binary tree) is one in which every non-leaf node has exactly two children.
Key relation: If L is the number of leaves and I is the number of internal (non-leaf) nodes, then L = I + 1. The total number of nodes N = I + L = (L - 1) + L = 2L - 1.
Given L = 19 leaves.
Compute total nodes: N = 2L - 1 = 2 × 19 - 1 = 38 - 1 = 37.
Conclusion: A strictly binary tree with 19 leaves has exactly 37 nodes.
A video solution is available for this question — log in and enroll to watch it.