Maximum Visible Inventory Path Sum
Flipkart's product catalog is structured hierarchically, often represented as a binary tree where each node signifies a product category. Each category holds an inventoryCount. To identify robust and well-stocked product lines, we define a "visible" sub-category as one whose inventoryCount is greater than or equal to its immediate parent's inventoryCount. This problem challenges you to find the maximum total inventory along a path from the top-level category (root) to any leaf category, where every step along the path maintains this "visibility" criterion.
Implement a function maxVisibleInventoryPathSum that takes the root of a binary tree representing product categories and returns the maximum possible sum of inventoryCount values along a valid "visible path". A path is considered valid if it starts at the root, ends at a leaf node, and for every non-root node N in the path, N.val >= Parent(N).val.
root: A TreeNode | null representing the root of the product category tree. Each TreeNode object has an integer property val (representing inventoryCount), and left and right properties, which can be TreeNode | null.inventoryCount values along any valid visible path from the root to a leaf. If no such path exists (e.g., an empty tree or no path satisfies the condition), return 0.root is null) should result in a return value of 0.root node and terminate at any leaf node.root node's value is always included in the path sum if a valid path exists.node.val >= parent.val) applies to all nodes on the path except the root. The root node itself is always considered "visible" to start a path.Examples
Example 1
Input:
root = [10,20,5,30,15,null,null]
Output:
60
Note:
The path 10 -> 20 -> 30 is valid (10 <= 20, 20 <= 30) and yields a sum of 60. Other paths either don't satisfy the condition (e.g., 10 -> 5 is invalid because 5 < 10) or yield smaller sums.
Example 2
Input:
root = [100]
Output:
100
Note:
The tree consists of a single node. The root itself is a leaf node, and the path sum is its value.
Example 3
Input:
root = [5,8,3,9,12,null,7,10,null,null,15]
Output:
40
Note:
The path 5 -> 8 -> 12 -> 15 is the valid visible path from root to leaf with the maximum sum of 40. Other paths like 5 -> 8 -> 9 -> 10 sum to 32, and 5 -> 3 is invalid (3 < 5).
Constraints
0 and 10^4.Node.val (inventoryCount) is an integer between 0 and 10^5.TreeNode structure is defined as:
class TreeNode {
val: number
left: TreeNode | null
right: TreeNode | null
constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
}
Loading editor...