What is the minimum number of children a non-root internal node can have in an M-way search tree?

In an M-way search tree, each internal node can have a minimum of $\lceil \frac{M}{2} \rceil$ children, where $M$ is the maximum number of children that each node can have.

Explanation:

1. Definition of M-way Search Tree: An M-way search tree is a variation of a binary tree where each node can have up to $M$ children.

2. Internal Nodes: These nodes are not leaf nodes; they have at least one child.

3. Minimum Children Requirement: For the tree to maintain balance and accommodate searching, the internal nodes must have at least half of the maximum number of children, rounded up. Therefore, it is stated mathematically as:

   $\text{Minimum number of children} = \lceil \frac{M}{2} \rceil$

Final Answer

Thus, the minimum number of children a non-root internal node can have in an M-way search tree is $\lceil \frac{M}{2} \rceil$.