Question

An M-way search tree is a generalization of which data structure?

• A. Binary search tree
• B. Graph
• C. Heap
• D. Complete binary tree

Hint:

Ask what happens when the branching factor M equals 2. A node then has one key and two children.

Answer 1

The Correct Option is A

Idea: Compare the defining rule of each option against the M-way rule.

An M-way search tree keeps keys ordered inside every node and routes a search down one of several child pointers based on key comparisons. A $graph$ has no ordering rule and allows cycles, so it is ruled out. A $heap$ only guarantees a parent-child ordering, not a left-right search ordering, so lookups by value are not supported. A complete binary tree is a shape constraint, not a search structure.

Only the binary search tree shares the exact ordered-search behaviour, and it appears when the branching factor is fixed at two:

\[M = 2 \;\Rightarrow\; \text{keys per node} = 1,\; \text{children} = 2\]

So the M-way search tree is the many-way extension of the binary search tree.

\[\boxed{\text{Binary search tree}}\]