Network models are widely applied to describe connectivity and flow in diverse systems. In contrast, the fact that many connected systems move through space as the result of dynamic restructuring has received little attention. Therefore, we introduce the concept of 'traveling networks', and we analyze a tree-based model where the leaves are stochastically manipulated to grow, branch, and retract. We derive how these restructuring rates determine key attributes of network structure and motion, enabling a compact understanding of higher-level network behaviors such as multiscale search. These networks self-organize to the critical point between exponential growth and decay, allowing them to detect and respond to environmental signals with high sensitivity. Finally, we demonstrate how the traveling network concept applies to real-world systems, such as slime molds, the actin cytoskeleton, and human organizations, exemplifying how restructuring rules and rates in general can select for versatile search strategies in real or abstract spaces.