Arborous Subtree Products — Problem Statement & Solution Guide
Problem Description
Given a tree with 'n' nodes, where each node has a value, find the maximum product of all values in the subtree rooted at each node. The product of a subtree is the product of all node values in the subtree.
Examples
Input
Given a tree with nodes [2, 3, 5, 4, 6], where each node has a value, find the maximum product of all values in the subtree rooted at each node.
Output
720
Explanation: Step-by-step: with input [2, 3, 5, 4, 6], we first calculate the product of the subtree rooted at node 0, which is 2 * 3 * 5 * 4 * 6 = 720. Then, we calculate the product of the subtree rooted at node 1, which is 3 * 4 * 6 = 72. Finally, we calculate the product of the subtree rooted at node 2, which is 5. The maximum product is 720.
Input
Given a tree with nodes [1, 2, 3, 4, 5], where each node has a value, find the maximum product of all values in the subtree rooted at each node.
Output
120
Explanation: Step-by-step: with input [1, 2, 3, 4, 5], we first calculate the product of the subtree rooted at node 0, which is 1 * 2 * 3 * 4 * 5 = 120. Then, we calculate the product of the subtree rooted at node 1, which is 2 * 4 = 8. Finally, we calculate the product of the subtree rooted at node 2, which is 3. The maximum product is 120.
Constraints
- 1 <= n <= 10^5
- Each node in the tree has a unique value between 1 and 10^6
- The input tree is a connected tree
- The values of the nodes are given in a separate list
Optimal Approach & Strategy
An optimized approach would involve using a depth-first search (DFS) to traverse the tree, keeping track of the product of values for each subtree, and updating the maximum product as needed. This approach would have a time complexity of O(n), where n is the number of nodes in the tree, and a space complexity of O(h), where h is the height of the tree.
Brute Force Approach
A brute force approach could involve calculating the product of all possible subtrees and comparing them to find the maximum product. This would involve generating all possible subtrees, calculating their products, and keeping track of the maximum product found. However, this approach would be inefficient due to its high time complexity.
Verified Code Solutions
function solution(tree) { let maxProduct = -Infinity; function dfs(node) { if (!node) return 1; let product = node.val * dfs(node.left) * dfs(node.right); maxProduct = Math.max(maxProduct, product); return product; } dfs(tree); return maxProduct; }class Solution { public: int maxProduct(TreeNode* root) { int max_product = INT_MIN; dfs(root, max_product); return max_product; } private: int dfs(TreeNode* node, int& max_product) { if (!node) return 1; int product = node->val * dfs(node->left, max_product) * dfs(node->right, max_product); max_product = max(max_product, product); return product; } }class Solution { int maxProduct = Integer.MIN_VALUE; public int maxProduct(TreeNode root) { dfs(root); return maxProduct; } private int dfs(TreeNode node) { if (node == null) return 1; int product = node.val * dfs(node.left) * dfs(node.right); maxProduct = Math.max(maxProduct, product); return product; } }class Solution: def maxProduct(self, root): max_product = [float('-inf')] def dfs(node): if not node: return 1 product = node.val * dfs(node.left) * dfs(node.right) max_product[0] = max(max_product[0], product) return product dfs(root) return max_product[0]function solution(tree) { let maxProduct = -Infinity; function dfs(node) { if (!node) return 1; let product = node.val * dfs(node.left) * dfs(node.right); maxProduct = Math.max(maxProduct, product); return product; } dfs(tree); 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.