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
- \( \frac{n - 2}{2} \)
- \( \frac{n - 1}{2} \)
- \( \frac{n}{2} \)
- \( \frac{n + 1}{2} \)
The Correct Option is B
Solution and Explanation
Top Questions on Trees
Consider the following algorithm someAlgo that takes an undirected graph \( G \) as input.
someAlgo(G) Let \( v \) be any vertex in \( G \).
1. Run BFS on \( G \) starting at \( v \). Let \( u \) be a vertex in \( G \) at maximum distance from \( v \) as given by the BFS.
2. Run BFS on \( G \) again with \( u \) as the starting vertex. Let \( z \) be the vertex at maximum distance from \( u \) as given by the BFS. 3. Output the distance between \( u \) and \( z \) in \( G \).
The output of tt{someAlgo(T)} for the tree shown in the given figure is ____________ . (Answer in integer)
In a B+- tree where each node can hold at most four key values, a root to leaf path consists of the following nodes:
\( A = (49, 77, 83, -) \)
\( B = (7, 19, 33, 44) \)
\( C = (20^*, 22^*, 25^*, 26^*) \)
The *-marked keys signify that these are data entries in a leaf. Assume that a pointer between keys \( k_1 \) and \( k_2 \) points to a subtree containing keys in \([ k_1, k_2 )\), and that when a leaf is created, the smallest key in it is copied up into its parent. A record with key value 23 is inserted into the B+- tree. The smallest key value in the parent of the leaf that contains 25* is __________ . (Answer in integer)A meld operation on two instances of a data structure combines them into one single instance of the same data structure. Consider the following data structures:
P: Unsorted doubly linked list with pointers to the head node and tail node of the list.
Q: Min-heap implemented using an array.
R: Binary Search Tree.
Which ONE of the following options gives the worst-case time complexities for meld operation on instances of size \( n \) of these data structures?Suppose the values 10, −4, 15, 30, 20, 5, 60, 19 are inserted in that order into an initially empty binary search tree. Let \( T \) be the resulting binary search tree. The number of edges in the path from the node containing 19 to the root node of \( T \) is __________. (Answer in integer)
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.
Questions Asked in GATE CS exam
The unit interval \((0, 1)\) is divided at a point chosen uniformly distributed over \((0, 1)\) in \(\mathbb{R}\) into two disjoint subintervals. The expected length of the subinterval that contains 0.4 is ___________. (rounded off to two decimal places)
- GATE CS - 2025
- Calculus
A quadratic polynomial \( (x - \alpha)(x - \beta) \) over complex numbers is said to be square invariant if \[ (x - \alpha)(x - \beta) = (x - \alpha^2)(x - \beta^2). \] Suppose from the set of all square invariant quadratic polynomials we choose one at random. The probability that the roots of the chosen polynomial are equal is ___________. (rounded off to one decimal place)
- GATE CS - 2025
- Probability
Consider the following C program:
- GATE CS - 2025
- Programming in C
Consider the following C program:
The output of the above program is __________ . (Answer in integer)
- GATE CS - 2025
- Programming in C
An application executes \( 6.4 \times 10^8 \) number of instructions in 6.3 seconds. There are four types of instructions, the details of which are given in the table. The duration of a clock cycle in nanoseconds is ____________. (rounded off to one decimal place)
