Frontend School

Swiggy Menu Price Eligibility

DSA
medium

Swiggy Menu Price Eligibility

Medium
Tree
DFS
Binary Tree
Recursion

Overview

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.

What you need to do / Task

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 & output

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:

  • A number representing the total count of 'discount eligible' nodes in the tree.

Clarifications

  • An empty tree (root is null) should result in a count of 0.
  • Node prices (val) will be non-negative integers.

Examples

1

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

  • Node 3 (root): Eligible. min_path_val for its children is 3. Count = 1.
  • Node 1 (left child of 3): 1 <= 3. Eligible. min_path_val for its children is 1. Count = 2.
  • Node 4 (right child of 3): 4 > 3. Not eligible (as 4 is not <= 3).
  • Node 3 (left child of 1): 3 > 1. Not eligible (as 3 is not <= 1).
  • Node 1 (left child of 4): 1 <= 3. Eligible. min_path_val for its children is 1. Count = 3.
  • Node 5 (right child of 4): 5 > 3. Not eligible (as 5 is not <= 3). Total eligible nodes: 3.
2

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

  • Node 9 (root): Eligible. min_path_val for its children is 9. Count = 1.
  • Node 3 (left child of 9): 3 <= 9. Eligible. min_path_val for its children is 3. Count = 2.
  • Node 1 (left child of 3): 1 <= 3. Eligible. min_path_val for its children is 1. Count = 3. Total eligible nodes: 3.
3

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

Constraints & assumptions

  • The number of nodes in the tree will be between 0 and 10^5.
  • TreeNode.val (price) will be between 0 and 10^9.
  • The input is guaranteed to be a valid binary tree.

Out of scope

  • Input validation (e.g., checking if root is actually a TreeNode or null).
  • Extensive memory optimization beyond the typical recursion stack.

What interviewers evaluate

  • Correctness of the algorithm for identifying 'discount eligible' nodes.
  • Efficiency of the solution in terms of time and space complexity.
  • Clarity and structure of the code, including proper handling of base cases and recursive logic.
  • Ability to articulate the approach and analyze its complexity.

Loading editor...