GATE 2025 CS (CS2) – Question 13
Programming and Data Structures · Trees and Binary Search Trees · 1 mark · Multiple choice
Consider a binary tree $T$ in which every node has either zero or two children. Let $n > 0$ be the number of nodes in $T$.
Which ONE of the following is the number of nodes in $T$ that have exactly two children?
- $\frac{n-2}{2}$
- $\frac{n-1}{2}$
- $\frac{n}{2}$
- $\frac{n+1}{2}$
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (B) $\frac{n-1}{2}$
Explanation
In a full binary tree, leaves = internal nodes + 1. So $n = 2i + 1$ and $i = (n-1)/2$.
More Trees and Binary Search Trees questions
- GATE 2025 CS (CS2) Q35 – Suppose the values 10, -4, 15, 30, 20, 5, 60, 19 are inserted in that order into an…
- GATE 2025 CS (CS2) Q38 – A meld operation on two instances of a data structure combines them into one single…
- GATE 2024 CS (CS2) Q39 – You are given a set V of distinct integers. A binary search tree T is created by inserting…
- GATE 2023 CS Q47 – Consider the C function foo and the binary tree shown. When foo is called with a pointer…
- GATE 2021 CS (CS1) Q20 – A binary search tree T contains n distinct elements. What is the time complexity of…
- GATE 2020 CS Q15 – The preorder traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19. Which…
All Trees and Binary Search Trees questions →