Efficient algorithm to find all distances to a specific node in a tree

Question

I wish to calculate the number of nodes within a certain distance of a particular node in a tree such as the one below:

Let's assume I'm looking for all the distances to node 2. What would be the most efficient (in terms of time complexity) method of computing the distances? Can it be done in linear time?

For this instance the output for the above tree would be:

• within one edge length distance: 4
• within two edge length distance: 2
• over two edge lengths away: 0

What I've done so far:

A simple brute force-ish solution would be to traverse the tree all the way to node 2 starting from all other nodes and counting the edges. I can make it a bit more efficient by storing the distances for all the nodes that are visited during each traverse and using the value if the node is visited again in a traverse that has originated from another node (for example traverses originating from nodes 1 and 3 in this graph will both result in visiting node 5). Is this the most efficient it can get?

Answer 1

Assuming your edges are not directed (which seems to be the case in case you are dealing with trees), you can calculate the distance by starting a breadth-first search from node 2. Then, you get the number of steps necessary to go from node 2 to each node $n$, which, as the graph is undirected, is the same as the number of steps necessary to go from node $n$ to 2.

If your had a directed graph, you can basically do the same, but you have to traverse edges in the opposite direction. E.g. if you are at node $n_1$, and have the edges $n_1 \to n_2$ and $n_3 \to n_1$, you would then process $n_3$ as a successor, but not $n_2$.