Algorithm to find the longest path in binary tree?

Question

Question:

You are given a rooted binary tree (each node has at most two children). For a simple path p between two nodes in the tree, let mp be the node on the path that is highest (closest to the root). Define the weight of a path w(p) = Σ_u∈p d(u, mp), where d denotes the distance (number of edges on the path between two nodes). That is, every node on the path is weighted by the distance to the highest node on the path.

The question asks an algorithm that finds the maximum weight among all simple paths in the tree. I'm not sure if I interpreted correctly, but can I just find the longest path from mp to the farthest node? I haven't figure out which algorithm is appropriate for this question, but I think recursive is one way to do it. Again, I don't understand the question very well, it would be better if someone could "translate" it for me and guide me to the solution.

Answer 1

Let's assume we know mp. Then the highest-weight path must start in the left subtree and end in the right subtree (or vice versa). Otherwise, the path would not be simple. To find the start and end node, we would go as deep as possible into the respective subtrees as each level adds depth to the weight. Therefore, we can compute the weight of this path directly from the heights of the two subtrees (by using the analytic solution of the arithmetic progression):

max_weight = height_left * (height_left + 1) / 2 + height_right * (height_right + 1) / 2

To find the maximum weight path across the entire tree (without prescribing mp), simply check this value for all nodes. I.e., take a recursive algorithm that calculates the height for each subtree. When you have the two subtree heights for a node, calculate the maximum weight. Of all these weights, take the maximum. This requires time linear in the number of nodes.

And to answer your question: No, it is not necessarily the longest path in the tree. The path can have one branch that goes very deep but a very shallow branch on the other side. This is because adding one level deeper to the path does not just increase the weight by 1 but by the depth of that node.

Answer 2

This problem is the diameter of a binary tree. In this case, the node that at the lower level has a greater weight because it's far from the root. Therefore, to find the longest path is to find the diameter of the binary tree. We can use brute force algorithm to solve it, by traveling all leaf-to-leaf paths, then arriving at the diameter.

Method: naive approach Find the height of left and right subtree, and then find the left and right diameter. Return the Maximum(Diameter of left subtree, Diameter of right subtree, Longest path between two nodes which passes through the root.) Time Complexity: Since when calculating the diameter, every iteration for every node, is calculating height of tree separately in which we iterate the tree from top to bottom and when we calculate diameter recursively so its O(N2)

Improve: If you notice at every node to find the diameter we are calling a separate function to find the height. We can improve it by finding the height of tree and diameter in the same iteration.Every node will return the two information in the same iteration , height of that node and diameter of tree with respect to that node. Running time is O(N)