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
A disk of size 512M bytes is divided into blocks of 64K bytes. A file is stored in the disk using linked allocation. In linked allocation, each data block reserves 4 bytes to store the pointer to the next data block. The link part of the last data block contains a NULL pointer (also of 4 bytes). Suppose a file of 1M bytes needs to be stored in the disk. Assume, 1K = \(2^{10}\) and 1M = \(2^{20}\). The amount of space in bytes that will be wasted due to internal fragmentation is ___________. (Answer in integer)
- GATE CS - 2025
- Memory hierarchy
- Given the sequence: \( 5, 6, 15, \_, 89, 170, 291 \), find the missing number.
- GATE CS - 2025
- Logical and Analytical Reasoning Skills
- Consider a five-digit number PQRST that has distinct digits P, Q, R, S, and T, and satisfies the following conditions:
1. \( P<Q \)
2. \( S>P>T \)
3. \( R<T \)
If integers 1 through 5 are used to construct such a number, the value of P is:- GATE ST - 2025
- GATE CS - 2025
- GATE MN - 2025
- GATE XE - 2025
- GATE XL - 2025
- mathematical reasoning
Three villages P, Q, and R are located in such a way that the distance PQ = 13 km, QR = 14 km, and RP = 15 km, as shown in the figure. A straight road joins Q and R. It is proposed to connect P to this road QR by constructing another road. What is the minimum possible length (in km) of this connecting road?
Note: The figure shown is representative.
- A business person buys potatoes of two different varieties P and Q, mixes them in a certain ratio and sells them at ₹192 per kg.
The cost of the variety P is ₹800 for 5 kg.
The cost of the variety Q is ₹800 for 4 kg.
If the person gets 8% profit, what is the P : Q ratio (by weight)?