Question:
Consider a binary tree \( T \) in which every node has either zero or two children.
Let \( n%gt;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?
Consider a binary tree \( T \) in which every node has either zero or two children.
Let \( n%gt;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?
Show Hint
For a full binary tree, the number of internal nodes (nodes with two children) is always
one less than the number of leaf nodes. Use the formula \( I = \frac{n-1}{2} \) for quick calculations in GATE.
Updated On: Jan 30, 2026
- \( \frac{n - 2}{2} \)
- \( \frac{n - 1}{2} \)
- \( \frac{n}{2} \)
- \( \frac{n + 1}{2} \)
Show Solution
Verified By Collegedunia
The Correct Option is B
Solution and Explanation
Given that every node in the binary tree has either zero or two children, this tree is known as a full binary tree.
For a full binary tree with \( n \) nodes, the number of leaf nodes (\( L \)) and internal nodes (\( I \)) (nodes with exactly two children) satisfy the relation:
\[
n = I + L
\]
A full binary tree with \( I \) internal nodes follows the property:
\[
L = I + 1
\]
Substituting \( L \) into the equation:
\[
n = I + (I + 1)
\]
\[
n = 2I + 1
\]
Solving for \( I \):
\[
I = \frac{n - 1}{2}
\]
Thus, the number of nodes with exactly two children is:
\[
\frac{n - 1}{2}
\]
which matches option (B).
Was this answer helpful?
0
0
Top GATE CS Programming and Data Structures Questions
- Which of the following sequences when stored in an array at locations A[1],..., A[10] forms a max-heap?
- Given N distinct elements in an array, determine the number of comparisons required to find the element which is not the largest:
Consider the following code:
main() { int x = 126, y = 105; { if (x > y) x = x - y; else y = y - x; } while (x != y) printf("%d", x); }- In a binary search tree with the following elements: \( 10, -4, 15, 13, 20, 5, 16, 19 \), the number of edges from node 19 to the root is?
Consider the following code:
int a; int arr[] = {30, 50, 10}; int *ptr = arr[10] + 1; a = *ptr; (*ptr)++; ptr = ptr + 1; printf("%d", a + arr[1] + *ptr);
View More Questions
Top GATE CS Trees Questions
- In a binary search tree with the following elements: \( 10, -4, 15, 13, 20, 5, 16, 19 \), the number of edges from node 19 to the root is?
Consider the following code:
int a; int arr[] = {30, 50, 10}; int *ptr = arr[10] + 1; a = *ptr; (*ptr)++; ptr = ptr + 1; printf("%d", a + arr[1] + *ptr);Consider the following hierarchical cache system with the following access times:
\[ \begin{array}{|c|c|c|} \hline \textbf{Cache Level} & \textbf{Hit Rate} & \textbf{Access Time} \\ \hline L1 & 90\% & 1 \text{ ns} \\ L2 & 80\% & 10 \text{ ns} \\ L3 & 100\% & 100 \text{ ns} \\ \hline \end{array} \]Find \( T_{avg} \) for hierarchical or simultaneous access.
- Consider a binary tree in which every node has either 0 or 2 children. Let \( N>0 \) be the number of nodes in the tree. The number of nodes that have exactly 2 children is:
What is the output of the following C code?
void foo(int *p, int x) { *p = x; } void main() { int *z; int a = 20, b = 25; z = a; // Incorrect: Should be z = a; foo(z, b); printf("%d", a); }Issue: The statement
z = a;is invalid becauseais an integer, andzis a pointer.
View More Questions
Top GATE CS Questions
- Which of the following sequences when stored in an array at locations A[1],..., A[10] forms a max-heap?
- The Lucas sequence Ln is defined by the recurrence relation: Ln = Ln−1 + Ln−2, for n ≥ 3, with L1 = 1 and L2 = 3. Which one of the options given is TRUE?
- Which of the following fields of IP header is/are always modified by any router before it forwards to IP Packet ?
- Which one of the following CIDR profix exactly represent the range of IP addresses 10.12.2.0 to 10.12.3.255?
- Consider an ethernet segment whose transmission is \(10^8\) bits per second. Maximum segment length \(500\ m\), speed of the provocation media velocity is \(2 × 10^8\) meter per second. What is the minimum frame size in bits ?
View More Questions