Given a full tree $\ T = (V, E, w) $ I need to find the path with maximum length from root $\\ s $ to any of the leaves.
I was thinking I could use some sort of BFS. Because I'm looking for maximum length path, I must go through all of the edges of the tree and I will start at the vertex $\ s $. So I'll use a dictionary $\ lengths = \{\} $ where each vertex in the $\ lengths $ dictionary is a key and its value is the total length from $\ s $ to that vertex. Then I'll just choose a the leaf with the highest value. From what I've seen online the solution to the problem is actually using Shortest path for DAG and multiply lengths by $\ -1 $ and the multiply back once algorithm finish. So not sure if my solution is ok?
Thanks,
EDIT: added proposed solution
weights = {}
def max_path(root, w):
if root in weights:
return weights[root]
else:
weights[root] = w + max(max_path(root.leftchild, root.weight), root.rightchild, root.weight))