K-heavy path approach
Filed under Amazon
Free read 2 of 3Understand the exact definition of a k-heavy path (is it root-to-leaf or any path?) and tree constraints.
The question
Given a tree structure where nodes contain numeric values, implement a recursive approach to find a 'k-heavy path', defined as a path where the sum of node values or a specific metric meets or exceeds a threshold k.
Constraints
- Tree can be n-ary or binary, assume general tree structure unless specified.
- Node values may be positive or negative.
- Time complexity of the recursion should be optimized.
Examples
- Input
- Tree: [1, [2, [4], [5]], [3]], k = 7
- Output
- True (Path 1 -> 2 -> 4 has sum 7)
- Why
- Traverse the tree recursively accumulating path sums until k is reached.
Approach
Understand the exact definition of a k-heavy path (is it root-to-leaf or any path?) and tree constraints.
Generate all possible paths from the tree and calculate their sums, leading to exponential time complexity.
Use depth-first search (DFS) with recursion, maintaining the running sum along the current path and returning early or recording success when the sum reaches k.
Empty tree, single node equal to k, and trees with negative weights affecting monotonic sums.
Tips
- What they are testing: Test with single-node trees, negative values, and cases where no path meets the threshold k.
- Common mistake: Failing to backtrack properly or resetting the path sum when exploring different branches in a recursive DFS.
Follow-ups
- Calculate the mathematical complexity of the recursion.
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.