Difference Between Maximum and Minimum Price Sum

Difference Between Maximum and Minimum Price Sum

What is this problem about?

In the Difference Between Maximum and Minimum Price Sum interview question, you are given an undirected tree where each node represents a city with a specific price. A "root" is chosen, and you calculate the price sum of all paths starting from this root to any other node. You need to find the maximum possible difference between the maximum path sum and the minimum path sum across all possible choices of the root node. In a tree, the minimum path sum for a root is always the price of the root node itself (the path from root to itself).

Why is this asked in interviews?

This "Hard" level problem is asked by companies like Media.net and Directi to evaluate a candidate's depth in Tree interview patterns and Dynamic Programming. It requires moving beyond a simple DFS to understanding how to re-root a tree or maintain multiple states (path with and without leaf) during a post-order traversal. It tests your ability to optimize what would be an $O(n^2)$ naive solution into a linear $O(n)$ one.

Algorithmic pattern used

This problem is solved using Dynamic Programming on Trees (specifically the Re-rooting technique or Diameter-like logic). You need to track two values for each subtree: the maximum path sum starting from the current node to a leaf, and the maximum path sum starting from the current node but excluding the actual leaf node. By combining these values from different branches at each node, you can calculate the maximum difference globally.

Example explanation

Imagine a tree: Node 1 (price 10) connected to Node 2 (price 5) and Node 3 (price 2). If Node 1 is root:

• Path 1-1: Sum 10 (Min path sum).
• Path 1-2: Sum 15.
• Path 1-3: Sum 12.
• Max Difference = $15 - 10 = 5$. If Node 2 is root:
• Path 2-2: Sum 5 (Min path sum).
• Path 2-1-3: Sum $5 + 10 + 2 = 17$ (Max path sum).
• Max Difference = $17 - 5 = 12$. The goal is to find the overall maximum, which is 12.

Common mistakes candidates make

• Brute Force: Running a DFS from every node, resulting in $O(n^2)$ time complexity, which will exceed the time limit for large trees.
• Leaf definition: Not correctly identifying that the minimum path is always the single node representing the root, or failing to exclude the leaf correctly in the path calculation.
• State Management: Forgetting to handle the "path to parent" when calculating the global max during a re-rooting pass.

Interview preparation tip

Study the Re-rooting DP pattern. It is a sophisticated technique where you first do a bottom-up pass to collect subtree info, then a top-down pass to propagate info from the rest of the tree to each node. This is the key to solving most "find property for every root" tree problems in linear time.