Minimum distance of nodes from a set of two nodes In an unweighted tree, suppose that we want to delete (or mark) any node which is closer to node $v$ than node $w$ ($dist(x,v) &lt; dist(x,w)$). The solution that comes to my mind is running two BFS, which gives us $\mathcal{O}(V + E)$ running time.  



Is there any better way to do this? possibly with one BFS?

EDIT: We can start two BFS from $w$ and $v$ simultaneously and one step at a time. First we find the nodes in distance 1 of the $w$ then the nodes in distance 1 of $v$ and then nodes at distance 2 of $w$ and so on. by the time there is no node in the queue of BFS of node $v$, we can end the search. any node which is first visited with $v$ BFS is closer to $v$ than $w$.  

But again I suppose there is a more efficient way to do this.
You can do this with only one BFS and the solution is very simple.  

I will assume that you have as input a graph $G = (V, E)$. Let $dist$ be a vector which stores the distance of all nodes of your graph to node $v \in V$.

You must run a BFS algorithm starting on node $v$ and store the distance from each node to $v$ in $dist$. This value can be simply obtained during the BFS execution. Then, you can iterate through this vector marking (or deleting) all nodes $i$ such that $dist[i]$ &lt; $dist[w]$. 

The overall complexity of this algorithm is $\mathcal{O}(V + E + V)$. In a tree, we have that $|E| = |V|-1$. Thus, the complexity is $\mathcal{O}(3 V) = \mathcal{O}(V)$.