Abstract
Ellis et al., proposed algorithms (in terms of vertexsep aration) to compute the node-search number of an n-vertextree T in O(n) time and to construct an optimal node-search strategy of T in O(n log n) time. An open problem is whether the latter can also be done in linear time. In this paper, we solve this open problem by exploring fundamental graph theoretical properties.