Swiggy Menu Price Eligibility
Swiggy is constantly optimizing its menu offerings and pricing strategies. Imagine a restaurant's menu structured as a binary tree, where each node represents a dish with an associated price. We're interested in identifying 'discount eligible' dishes—those that fit into a continuous 'discount chain' from the root of the menu hierarchy. This helps in understanding menu flow and potential promotional strategies.
Implement a function countDiscountEligibleNodes that takes the root of a binary tree representing a menu and returns the total count of 'discount eligible' nodes.
A node X is considered 'discount eligible' if its price is less than or equal to the price of every node on the path from the root to X (excluding X itself). The root node is always considered 'discount eligible' as it starts any potential discount chain.
Input:
root: A TreeNode | null representing the root of the binary tree. Each TreeNode has a val property (representing the dish's price, a number) and left and right properties (references to child TreeNodes or null).Output:
number representing the total count of 'discount eligible' nodes in the tree.root is null) should result in a count of 0.val) will be non-negative integers.Examples
Example 1
Input:
root = [3,1,4,3,null,1,5]
Output:
3
Note:
The tree looks like:
3 (eligible, min_path_val=3)
/
1 4
/ /
3 1 5
Example 2
Input:
root = [9,3,null,1,null,null,2]
Output:
3
Note:
The tree looks like:
9 (eligible, min_path_val=9)
/
3 null
/
1 null
Example 3
Input:
root = [1]
Output:
1
Note:
The tree only contains the root node (1). The root is always eligible. Total eligible nodes: 1.
Constraints
TreeNode.val (price) will be between 0 and 10^9.root is actually a TreeNode or null).Loading editor...