I am looking for an algorithm with time complexity in $\mathcal O(|V|)$ that determines whether a given graph $G=(V,E)$ is a caterpillar tree.
A caterpillar tree is a tree that has a path to which all nodes are connected by a maximum of one edge. So for every vertex v there is a vertex u on the path so that the disctance between v und u is at most 1. In other words, removing all the leaves results in a simple path.
The only progress I've made so far is that I could use breadth-first search or depth-first search to traverse the graph. They have a complexity of $\mathcal O(|V|+|E|)$, but in a caterpillar tree, $|E|=|V|-1$, so I end up in $\mathcal O(2|V|)$ = $\mathcal O(|V|)$.
Is that idea correct? If so, then how can I modify BFS/DFS to do what I want? I am thinking of adding a branch depth counter of some sort and allowing only one branch with length >1 (the central path of the caterpillar), but I have no idea how to implement that without changing the original algorithm too much.