Given a graph with edge costs and vertex profits and given a budget B, the Orienteering Problem asks for a walk of cost at most B of maximum profit. Additionally, each profit may be given with a time window within which it can be collected by the walk. While the Orienteering Problem and thus the version with time windows are NP-hard in general, it remains open on numerous special graph classes. Since in several applications, especially for planning a route from A to B with waypoints, the input graph can be restricted to tree-like or path-like structures, in this paper we consider orienteering on these graph classes. While the Orienteering Problem with time windows is NP-hard even on undirected paths and cycles, and remains so even if all profits must be collected, we show that for directed paths it can be solved in \(\mathcal {O}(m \log m)\) time (where m is the total number of time windows), even if each profit can be collected in one of several time windows. The same case is shown to be NP-hard for directed cycles. Particularly interesting is the Orienteering Problem on a directed cycle with one time window per profit. We give an efficient algorithm for the case where all time windows are shorter than the length of the cycle, resulting in a 2-approximation for the general setting. Based on the algorithm for directed paths, we further develop a polynomial-time approximation scheme for this problem. For the case where all profits must be collected, we present an \(\mathcal {O}(n^4)\) -time algorithm. For the Orienteering Problem with time windows for the edges, we give a quadratic time algorithm for undirected paths and observe that the problem is NP-hard for trees. In the variant without time windows, we show that on trees and thus on graphs with bounded tree-width the Orienteering Problem remains NP-hard. We present, however, an FPT algorithm to solve orienteering with unit profits that we then use to obtain a ( \(1+\varepsilon \) )-approximation algorithm on graphs with arbitrary profits and bounded tree-width, which improves current results on general graphs.