Q1GATE 2015MCQ

If a node has $K$ children in B tree, then the node contains exactly _____ keys.

📖 Explanation

In a B-tree, the structure of a node is defined by a strict relationship between the number of keys and the number of child pointers.
Let $n$ represent the number of keys contained within a specific node.
According to the fundamental properties of B-trees, a node that contains $n$ keys will always have exactly $n+1$ children to maintain the search tree structure.
Given that the node has $K$ children, we can establish the equation $n+1 = K$ .
Solving for $n$ , we find $n = K - 1$ , which represents the total number of keys in that node.

Q2GATE 2008MCQ

A B-tree of order 4 is built from scratch by 10 successive insertions. What is the maximum number of node splitting operations that may take place?

🚀 Solve in Practice Mode

📖 Explanation

A B-tree of order $m=4$ splits nodes when they reach $m=4$ keys. The number of splits is maximized when insertions occur in a sequence that causes the rightmost leaf to split repeatedly, potentially triggering cascading splits at the parent level.

Insertions 1-3 fill the root; insertion 4 causes the first split.
Insertion 6 causes a leaf split and promotes a key, triggering a 2nd split.
Insertion 8 causes a leaf split and promotes a key, triggering a 3rd split.
Insertion 10 causes a leaf split (4th split), promoting a key into a full root $\{2, 4, 6, 8\}$ , which splits into two nodes (5th split).

Thus, the maximum number of node splitting operations is 5.

Q4MSQ

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: A 2-3 tree is such that a. All internal nodes have either 2 or 3 children b. All paths from root to the leaves have the same length. The number of internal nodes of a 2-3 tree having 9 leaves could be

🚀 Solve in Practice Mode

📖 Explanation

For a 2-3 tree with $L$ leaves, let $n_2$ be the number of nodes with 2 children and $n_3$ be the number of nodes with 3 children. The total number of edges is $2n_2 + 3n_3$ , which must equal the total number of nodes minus 1. Since total nodes $N = n_2 + n_3 + L$ , the relationship is $2n_2 + 3n_3 = n_2 + n_3 + L - 1$ , simplifying to $n_2 + 2n_3 = L - 1$ .
Given $L=9$ , we have $n_2 + 2n_3 = 8$ . The total number of internal nodes is $N = n_2 + n_3$ . Substituting $n_2 = N - n_3$ into the equation gives $(N - n_3) + 2n_3 = 8$ , or $N = 8 - n_3$ .

If $n_3 = 4$ , then $N = 8 - 4 = 4$ , which corresponds to Option A.
If $n_3 = 1$ , then $N = 8 - 1 = 7$ , which corresponds to Option D.
Both $N=4$ and $N=7$ are valid configurations for a 2-3 tree with 9 leaves.

[CORRECT_OPTION: A, D]

B Tree Practice Questions

Get the full B Tree experience — 100% free