Frontend School

Maximum Visible Inventory Path Sum

DSA
medium

Maximum Visible Inventory Path Sum

Medium
Tree Traversal
Depth-First Search
Binary Tree

Overview

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.

What you need to do / Task

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.

Input & output

  • Input: 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.
  • Output: An integer, representing the maximum sum of 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.

Clarifications

  • An empty tree (root is null) should result in a return value of 0.
  • The path must originate from the root node and terminate at any leaf node.
  • The root node's value is always included in the path sum if a valid path exists.
  • The visibility condition (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

1

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.

2

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.

3

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

Constraints & assumptions

  • The number of nodes in the tree is between 0 and 10^4.
  • Node.val (inventoryCount) is an integer between 0 and 10^5.
  • The tree is a binary tree; it is not necessarily balanced.
  • The 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)
        }
    }
    

What interviewers evaluate

  • Correctness of the recursive tree traversal (Depth-First Search) implementation.
  • Accurate application of the visibility condition between parent and child nodes.
  • Proper handling of base cases, including empty trees and leaf nodes.
  • Efficiency of the solution in terms of time and space complexity.

Loading editor...