0
$\begingroup$

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))
$\endgroup$
1
  • $\begingroup$ Some problems have more than one solution. Can you prove that your solution works? This is how we ascertain things in math. $\endgroup$ – Yuval Filmus Jan 1 at 14:57
2
$\begingroup$

Your solution will work and, if implemented properly, will require $O(n)$ time where $n$ is the number of vertices of $T$ (to achieve this complexity you cannot just use a BST or a hashmap as a dictionary though). Notice that you're using the fact that there is a unique path from the root of $T$ to each of the leaves.

Also running any shortest-path algorithm for DAGs on the weighted version of $T$ in which each edge $e$ weighs $-w(e)$ will work in $O(n)$ time. However this is overcomplicated as it requires finding a topological order of $T$ (which requires a DFS). In other words you are not taking advantege of the fact that $T$ is a tree and not just a generic DAG.

A quick way to solve this problem in $O(n)$ time is performing a depth first search starting from the root of $T$ while keeping track of the weighted depth $d$ of the current vertex. Whenever you traverse an edge $e$ "forward" (i.e., from a vertex to one of its children) you increase $d$ by $w(e)$, whenever you traverse an edge $e$ "backwards" (from a vertex to its parent) you decrease $d$ by $w(e)$. It is very easy to implement this recursively.

$\endgroup$
2
  • $\begingroup$ Thanks for a great explanation. But I'm not sure I understand how come DFS will be $\ O(n) $. Wouldn't DFS traverse some vertexes more than once ? $\endgroup$ – bm1125 Jan 1 at 16:00
  • $\begingroup$ It is easy to see that the time spent during the DFS is proportional to the number of edge traversals. Each edge is traversed twice (one time "forward" and one time "backwards"), and there are exactly $n-1$ edges in a tree. The number of traversals is then $2n-2$ and the time complexity is $O(n)$. $\endgroup$ – Steven Jan 1 at 17:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.