We investigate whether a spatial representation of a search task supports 4- to 7-year-old children's information-search strategies, relative to their performance in a question-asking game. Children played two computationally and structurally analogous search games: a spatial search task, the maze-exploration game, in which they had to discover the path through a maze by removing masks covering its passages; and a "verbal search task," the 20-questions game, where they had to identify a target monster from a set of eight monsters by asking yes-no questions. Across four experiments, we found that children searched more efficiently when they could make queries nonverbally (Experiments 1 and 2a). We also found that merely providing children with a visual conceptual aid that supports their representation of the hypothesis space (Experiment 2b), or familiarizing them with the hypothesis-space structure (Experiment 3) was not sufficient to improve their search strategies. Together, our results suggest that young children's difficulties in the 20-questions game are mainly driven by the verbal requirements of the task. However, they also demonstrate that efficient search strategies emerge much earlier than previously assumed in tasks that do not rely on verbal question generation. These findings highlight the importance of developing age-appropriate paradigms that capture children's early competence, in order to gain a more comprehensive picture of their emerging information-search abilities.