Tree: Depth-First Search - Binary Tree Maximum Path Sum
Suppose the problem is modified so that the maximum path sum must be computed in a binary tree where edges have weights (instead of nodes), and the path can start and end at any node. Which approach best handles this variant?
AUse the same node-based recursive postorder DFS, summing node values.
BConvert edge weights to node weights by assigning edge weight to child node and apply standard max path sum.
CUse breadth-first search to find maximum weighted path.
DModify DFS to compute max gain based on edge weights, tracking gains along edges rather than nodes.
Step-by-Step Solution
Solution:
Step 1: Understand problem change
Edge weights replace node values, so path sums depend on edges, not nodes.
Step 2: Evaluate approaches
Node-based DFS summing node values is invalid; converting edge weights to nodes is ambiguous; BFS or DFS on edges with tracking is needed.
Step 3: Choose best approach
BFS or DFS adapted to edge weights can find max weighted path; standard node-based recursion won't work directly.
