Frontend School

Max Adjusted Path Cost in Binary Tree

DSA
medium

Max Adjusted Path Cost in Binary Tree

Medium
Tree Traversal
Depth-First Search
Binary Tree

Overview

At Livspace, optimizing the design and assembly process for modular furniture is crucial for efficiency and customer satisfaction. Each design project can be broken down into a hierarchy of modules, represented as a binary tree. To better manage costs and resource allocation, we need to analyze the "projected cost" of different design paths. Some modules are designated as "critical" due to their significant impact or specialized requirements, and their costs are treated differently.

What you need to do / Task

Your task is to implement a function that calculates the maximum possible "adjusted total cost" among all root-to-leaf paths in a given binary tree.

  1. Traverse the tree to explore all root-to-leaf paths.
  2. For each node in a path, determine its "adjusted cost":
    • If the node's val (cost) is present in the criticalValues list, its contribution to the path sum is doubled.
    • Otherwise, it contributes its val normally.
  3. Sum these adjusted costs for each complete root-to-leaf path.
  4. Return the maximum adjusted total cost found among all paths.

Input & output

Input:

  • root: A TreeNode object representing the root of the binary tree. Each TreeNode has a val (number) and left, right pointers (TreeNode | null). The val represents the module's base cost.
  • criticalValues: An array of numbers, where each number represents a val that, if encountered in a node, signifies a critical module.

Output:

  • A single number representing the maximum adjusted total cost found among all root-to-leaf paths. If the tree is empty (root is null), return 0.

Clarifications

  • Empty Tree: If the root is null, the function should return 0.
  • Single Node Tree: A single node is considered a root-to-leaf path.
  • criticalValues List: The criticalValues list can be empty. If so, no module costs will be doubled. Values in criticalValues are guaranteed to be positive integers, as are node vals.
  • Node Values: All TreeNode.val will be positive integers.

Examples

1

Example 1

Input:

root = [10,5,20,1,null,7], criticalValues = [5]

Output:

37

Note:

Paths:

  • 10 -> 5: Adjusted cost = 10 (normal) + (5 * 2) (critical) = 10 + 10 = 20.
  • 10 -> 20 -> 1: Adjusted cost = 10 (normal) + 20 (normal) + 1 (normal) = 31.
  • 10 -> 20 -> 7: Adjusted cost = 10 (normal) + 20 (normal) + 7 (normal) = 37. The maximum adjusted path cost is 37.
2

Example 2

Input:

root = [1,2,3,4,5], criticalValues = [1,3]

Output:

9

Note:

Paths:

  • 1 -> 2 -> 4: Adjusted cost = (1 * 2) (critical) + 2 (normal) + 4 (normal) = 2 + 2 + 4 = 8.
  • 1 -> 2 -> 5: Adjusted cost = (1 * 2) (critical) + 2 (normal) + 5 (normal) = 2 + 2 + 5 = 9.
  • 1 -> 3: Adjusted cost = (1 * 2) (critical) + (3 * 2) (critical) = 2 + 6 = 8. The maximum adjusted path cost is 9.
3

Example 3

Input:

root = [100], criticalValues = [100]

Output:

200

Note:

The only path is 100. Since 100 is in criticalValues, its cost is doubled: 100 * 2 = 200.

Constraints

Constraints & assumptions

  • The number of nodes in the tree will be between 0 and 10^4.
  • TreeNode.val will be between 1 and 10^5.
  • The length of criticalValues array will be between 0 and 10^4.
  • criticalValues[i] will be between 1 and 10^5.
  • The tree structure is guaranteed to be valid (no cycles).
  • The maximum adjusted path cost can fit within a standard 32-bit integer.

Out of scope

  • Handling negative node values or critical values (guaranteed positive).
  • Validating the input tree structure for cycles or invalid node types.

What interviewers evaluate

  • Algorithmic Correctness: Does the solution correctly identify and sum adjusted costs for all root-to-leaf paths?
  • Tree Traversal Logic: Is the chosen traversal method (e.g., DFS) correctly applied to explore all paths?
  • Efficiency: Is the solution optimized for time complexity, especially regarding criticalValues lookups?
  • Edge Case Handling: Does the code gracefully handle empty trees or single-node trees?

Loading editor...