Question:
An M-way search tree is a generalization of which data structure?
An M-way search tree is a generalization of which data structure?
Show Hint
Ask what happens when the branching factor M equals 2. A node then has one key and two children.
Updated On: Jul 2, 2026
- Binary search tree
- Graph
- Heap
- Complete binary tree
Show Solution
Verified By Collegedunia
The Correct Option is A
Solution and Explanation
Step 1: Recall what a binary search tree stores. Each node has at most one key and at most two children, and the key splits the values into a smaller-left and larger-right group.
Step 2: An M-way search tree relaxes the branching limit. Each node can hold up to \(M-1\) keys and can have up to \(M\) children. The keys inside a node are sorted, and they partition the search range into \(M\) intervals.
Step 3: Set \(M=2\). Then a node holds \(M-1=1\) key and has \(M=2\) children, which is exactly a binary search tree.
Step 4: Since the M-way search tree reduces to a binary search tree at \(M=2\), it is the direct generalization of the binary search tree. The correct option is (A).
Step 2: An M-way search tree relaxes the branching limit. Each node can hold up to \(M-1\) keys and can have up to \(M\) children. The keys inside a node are sorted, and they partition the search range into \(M\) intervals.
Step 3: Set \(M=2\). Then a node holds \(M-1=1\) key and has \(M=2\) children, which is exactly a binary search tree.
Step 4: Since the M-way search tree reduces to a binary search tree at \(M=2\), it is the direct generalization of the binary search tree. The correct option is (A).
Was this answer helpful?
0
0
Top CPET Computer Science Questions
- Which of the following is a key reason for choosing DRAM over SRAM for main memory?
- Which of the following components in an FPGA is responsible for implementing combinational and sequential logic?
- What is the main purpose of declaring a base class as virtual in multiple inheritance?
- What happens if a class contains at least one pure virtual function?
- What happens if a derived class defines a function with the same name as a base class function, but with a different parameter list?
View More Questions
Top CPET Data Structures - Binary Search Tree Questions
- Which is the best data structure to represent a sparse matrix?
- The time complexity to perform an Enqueue operation on a Queue data structure is:
- The Postorder traversal of a Binary Search tree which is created by presenting the values in the order 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 will be:
- Which one of the following is the correct way to increment the rear end of a circular queue represented as an array of size M?
Top CPET Questions
- Which of the following is a key reason for choosing DRAM over SRAM for main memory?
- Which of the following components in an FPGA is responsible for implementing combinational and sequential logic?
- What is the main purpose of declaring a base class as virtual in multiple inheritance?
- What happens if a class contains at least one pure virtual function?
- What happens if a derived class defines a function with the same name as a base class function, but with a different parameter list?
View More Questions