Path Sum (Binary Tree)

To solve the Path Sum problem efficiently, I would use a recursive Depth-First Search strategy. First, I'd clarify with the interviewer if the tree values are strictly positive, which could allow for early termination if the running sum exceeds the target. Assuming general integer inputs, my approach involves traversing from the root to every leaf, tracking the cumulative sum along the path. I will define a helper function that takes the current node and the remaining target sum. The logic flows as follows: if the current node is null, we return false immediately since no path exists here. If the node is a leaf, meaning it has no children, we check if the node's value exactly equals the remaining target sum. If they match, we have found our valid path and return true. For non-leaf nodes, we subtract the current node's value from the target sum and recursively check both the left and right subtrees. The function returns true if either the left or right recursive call finds a valid path. This naturally handles the backtracking required to explore all possibilities. In terms of complexity, this runs in O(N) time because in the worst case, we visit every node once. The space complexity is O(H), representing the maximum depth of the recursion stack, which is optimal for this traversal pattern. This solution is clean, avoids global state, and aligns well with Google's emphasis on efficient, readable algorithms.