The number of leaf nodes in a rooted tree of n nodes, with each node having 0…
20242022
The number of leaf nodes in a rooted tree of n nodes, with each node having 0 or 3 children is:
- A.
n/2
- B.
(n-1)/3
- C.
(n-1)/2
- D.
(2n+1)/3
Attempted by 208 students.
Show answer & explanation
Correct answer: D
Explanation:
Let L be the number of leaf nodes and I be the number of internal nodes, then following relation holds for above given tree
L = (3-1)I + 1 = 2I + 1
Total number of nodes(n) is sum of leaf nodes and internal nodes
n = L + I
After solving above two, we get L = (2n+1)/3