DFS on a Tree

general
, ,
1

I just have a doubt. Can we use DFS to find the shortest path between two nodes in a tree?
If yes, then how should we tweak the DFS to achieve the desired result?

1 Like
2

there are other algo also djsitra and bellmon ford

3

But I don’t want to use them (at least now). If it can be done with DFS (if possible) then I will be happy using DFS. I am just curious whether it can be done using DFS, I know that there are other algorithms as well.

4

@everule1 Please help.

5

You certainly can not find shortest path using DFS, there will be some modifications in the code and that will ultimately become BFS instead.

6

let dist[u][v] be the distance between two nodes u & v, r be the root of the tree from where you are starting the dfs & l be the least common ancestor of u and v so we can write that
dist[u][v]=dist[u][r]+dist[v][r]-2dist[l][r]
you can find dist[u][r] for all nodes by doing a simple dfs, please tell if something seems wrong

7

A dfs won’t get you the shortest path unless you use binary lifting, you have to use a bfs. Which will still be O(n).
If you want to calculate it quickly using binary lifting, find the depth of the 2 nodes, and subtract the depth of it’s LCA twice, which can be found in O(log n)
Binary lifting

1 Like
8

Thanks to everyone for helping me. :slightly_smiling_face:

9

FCTRE flasbacks