Frontend School

Conditional Travel Package Value

DSA
medium

Conditional Travel Package Value

Medium
Tree
Traversal
Binary Tree
DFS

Overview

MakeMyTrip offers complex travel packages which can be represented as hierarchical structures (binary trees). Each node in this tree represents a component of the package with an associated value (e.g., cost, profit, rating). To optimize package offerings, we need to calculate the total value of a package, but with a specific business rule: certain "negative impact" components might invalidate their sub-components if they appear consecutively.

What you need to do / Task

Implement a function calculateConditionalPackageValue that takes the root of a binary tree as input. The function should traverse the tree and calculate the sum of values of all nodes that are part of a 'valid' path from the root. A path is considered 'valid' for a node if its value is included based on the following rules:

  1. The root node always contributes its value to the total sum.
  2. For any other node (non-root):
    • Its value is always included if its immediate parent's value was non-negative (zero or positive).
    • If its immediate parent's value was negative, the current node's value is included ONLY if the current node's value itself is non-negative.
    • If both its immediate parent's value AND the current node's value are negative, then the current node and all its descendants (on this path) are considered 'invalid'. Their values should NOT be included in the total sum.

Input & output

  • Input: root: TreeNode | null - The root of a binary tree. Each TreeNode has an integer val.
  • Output: number - The total sum of values of all valid nodes in the tree according to the rules.

Clarifications

  • An empty tree (root is null) should result in a total sum of 0.
  • Node values can be positive, negative, or zero.
  • The 'invalidation' rule applies recursively: once a node is deemed 'invalid' due to consecutive negatives, none of its children or further descendants on that specific path will contribute to the sum.

Examples

1

Example 1

Input:

root = [10,5,-3,-2,7,null,11]

Output:

28

Note:

The tree is: 10 /
5 -3 / \
-2 7 11

  • Path 10 -> 5 -> -2: All included (10, 5, -2) because no consecutive negatives.
  • Path 10 -> 5 -> 7: All included (10, 5, 7) because no consecutive negatives.
  • Path 10 -> -3 -> 11: All included (10, -3, 11) because -3 has a non-negative parent (10), and 11 has a negative parent (-3) but 11 itself is non-negative. Total valid sum = 10 + 5 + (-2) + 7 + (-3) + 11 = 28.
2

Example 2

Input:

root = [1,-5,2,-3,-4,null,6]

Output:

4

Note:

The tree is: 1 /
-5 2 / \
-3 -4 6

  • Path 1 -> -5 -> -3: Node -3 is excluded because its parent (-5) is negative, and -3 itself is negative. All descendants of -3 are also excluded.
  • Path 1 -> -5 -> -4: Node -4 is excluded because its parent (-5) is negative, and -4 itself is negative. All descendants of -4 are also excluded.
  • Path 1 -> 2 -> 6: All included (1, 2, 6) because no consecutive negatives. Total valid sum = 1 + (-5) + 2 + 6 = 4.
3

Example 3

Input:

root = [-10]

Output:

-10

Note:

The tree consists only of the root node -10. The root node always contributes its value, so the sum is -10.

Constraints

Constraints & assumptions

  • The number of nodes in the tree will be between 0 and 10^4.
  • Node values (val) will be between -1000 and 1000.
  • The tree structure is a valid binary tree.

What interviewers evaluate

  • Correctness of Logic: Accurately implements the conditional sum rules for all nodes and paths.
  • Tree Traversal Strategy: Demonstrates efficient and correct use of tree traversal (e.g., Depth-First Search).
  • Edge Case Handling: Correctly handles an empty tree, a single-node tree, and paths with various positive/negative value combinations.
  • Code Structure & Readability: Writes clean, well-organized, and understandable code with appropriate variable names.

Loading editor...