Maximum Path Product in a Tree — Problem Statement & Solution Guide
Problem Description
Given a tree where each node has a value, find the maximum product of node values along any path from the root to a leaf node, with the path consisting of distinct nodes.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Maximum Path Product in a Tree"
WHY DOES IT MATTER?
Root‑to‑leaf DP on trees captures a wide class of optimization problems where decisions accumulate along a hierarchical structure. Mastering this pattern lets you solve cost‑minimization, probability, and resource‑allocation tasks that appear in networking, compilers, and game AI.
OPTIMIZATION CHALLENGE
The breakthrough is recognizing that the product of a prefix can be reused for all its descendants, eliminating exponential recomputation. By propagating a single cumulative value (or a pair for sign handling) during a DFS, we achieve linear time and only O(H) auxiliary space.
REAL-WORLD CONNECTION
Consider a distributed microservice call chain where each service adds a latency factor. Finding the worst‑case end‑to‑end latency is analogous to maximizing the product of latency multipliers along a call tree, guiding capacity planning and SLA verification.
During the interview, write the DFS as a clean recursive helper that returns the current product; keep a global variable for the answer. If you suspect overflow, switch to 64‑bit integers or logarithms, and always discuss zero/negative handling before coding.
COMPLEXITY AT A GLANCE
O(N)O(H)Core Theory — Why This Approach?
The problem reduces to finding a root‑to‑leaf path that maximizes the multiplicative aggregate of node values. A naïve enumeration of all root‑to‑leaf paths incurs exponential time because a tree with branching factor b and depth d can have O(b^d) leaves. Moreover, recomputing the product for overlapping prefixes wastes work. The optimal paradigm is a single‑pass depth‑first search (DFS) that carries the cumulative product from the root downwards. At each node we multiply the incoming product by the node’s value, and when a leaf is reached we compare the resulting product with a global maximum. This is a classic example of tree DP where the state (the best product so far) is propagated along the recursion stack, yielding linear time. If values can be negative or zero, we must track both the maximum and minimum products because a negative * negative can become positive; this mirrors the “maximum product subarray” technique extended to trees.
Interview Questions on This Problem
Q1How would you modify the solution if node values can be negative and you need the maximum absolute product?
Maintain two DP values per node: the maximum product and the minimum product achievable from the root to that node. When processing a child, compute new candidates by multiplying the child’s value with both the parent’s max and min, then update the child’s max/min accordingly. The answer is the maximum absolute value among all leaf candidates.
Q2Can you solve the problem in O(1) extra space besides the input tree?
Yes, by performing an iterative DFS using the tree’s parent pointers (or by temporarily modifying the adjacency list) and storing only the current product on the call stack. The recursion stack itself accounts for O(H) space, which is O(1) extra if the tree is stored in place and H is bounded by log N for balanced trees.
Q3What changes are required if the path may start at any node and end at any descendant (not necessarily the root)?
Perform a post‑order DP where each node returns the best product of any path that starts at that node and goes downwards. For each node, combine its value with the best child product (or start a new path) and propagate the global maximum upward. This still runs in O(N) time.
Examples
Input
{1, {2, {3, {4, {5}}}}, {6, {7, {8}}}}Output
12
Explanation: Step-by-step: Given the tree {1, {2, {3, {4, {5}}}}, {6, {7, {8}}}}, we start at the root node 1. The maximum product of distinct nodes from the root to a leaf node is 1 * 3 * 4 = 12.
Input
{1, {2, {3, {4}}}, {5, {6, {7, {8}}}}}Output
6
Explanation: Step-by-step: Given the tree {1, {2, {3, {4}}}, {5, {6, {7, {8}}}}}, we start at the root node 1. The maximum product of distinct nodes from the root to a leaf node is 1 * 2 * 3 = 6.
Constraints
- The tree is guaranteed to be non-empty.
- Each node has at most two children (left child and right child).
- The number of nodes in the tree will not exceed 1000.
- Each node's value will be between -10^5 and 10^5.
Optimal Approach & Strategy
Perform a DFS that propagates the cumulative product down the tree, updating a global maximum at each leaf; this runs in linear time.
Brute Force Approach
Enumerate every root‑to‑leaf path, compute its product, and keep the maximum; this requires exponential time in the worst case.
Verified Code Solutions
function solution(root) {
if (!root) return 0;
if (!root.left && !root.right) return root.val;
let maxProduct = 0;
function dfs(node, product) {
if (!node) return;
product *= node.val;
if (!node.left && !node.right) {
maxProduct = Math.max(maxProduct, product);
}
dfs(node.left, product);
dfs(node.right, product);
}
dfs(root, 1);
return maxProduct;
}class Solution {
public:
int solution(TreeNode* root) {
if (!root) return 0;
if (!root->left && !root->right) return root->val;
int maxProduct = 0;
void dfs(TreeNode* node, int product) {
if (!node) return;
product *= node->val;
if (!node->left && !node->right) {
maxProduct = std::max(maxProduct, product);
}
dfs(node->left, product);
dfs(node->right, product);
}
dfs(root, 1);
return maxProduct;
}
};class Solution {
public int solution(TreeNode root) {
if (root == null) return 0;
if (root.left == null && root.right == null) return root.val;
int maxProduct = 0;
public void dfs(TreeNode node, int product) {
if (node == null) return;
product *= node.val;
if (node.left == null && node.right == null) {
maxProduct = Math.max(maxProduct, product);
}
dfs(node.left, product);
dfs(node.right, product);
}
dfs(root, 1);
return maxProduct;
}
}def solution(root):
if not root: return 0
if not root.left and not root.right: return root.val
max_product = 0
def dfs(node, product):
if not node: return
product *= node.val
if not node.left and not node.right:
nonlocal max_product
max_product = max(max_product, product)
dfs(node.left, product)
dfs(node.right, product)
dfs(root, 1)
return max_productfunction solution(root) {
if (!root) return 0;
if (!root.left && !root.right) return root.val;
let maxProduct = 0;
function dfs(node, product) {
if (!node) return;
product *= node.val;
if (!node.left && !node.right) {
maxProduct = Math.max(maxProduct, product);
}
dfs(node.left, product);
dfs(node.right, product);
}
dfs(root, 1);
return maxProduct;
}Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.