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?