Binary Tree Path Sum — Amazon Coding Question Guide

You are given a binary tree of integers and a target sum S. The problem progresses in three practical stages: first check whether any root-to-leaf path adds up to S, then return one such root-to-leaf path, and finally relax the start point so the path may start at any node and proceed downward (parent->child) to sum to S.

In an interview you'll typically be walked through these stages in order. Start by explaining a recursive DFS approach that subtracts node values from the remaining sum and checks leaf nodes. Next, extend that DFS with backtracking (or maintain a path stack) to return the actual node-value list for a successful root-to-leaf path. For the final stage, discuss traversing every node as a potential path start and using either nested DFS or the O(n) prefix-sum + hashmap trick to find a downward path that sums to S.

Skills you should demonstrate: tree traversal (DFS), backtracking to construct paths, careful base-case and null handling, working with negative values, and an efficient prefix-sum optimization to reduce from O(n^2) to O(n). Be ready to explain iterative vs recursive implementations, space/time complexity tradeoffs, and how you would adapt your solution to return all matching paths or just count them.