Longest path on a full tree

Question

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))

Steven · Accepted Answer

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.

Longest path on a full tree

One Answer

Add your own answers!

Ask a Question