Path Sum - Video Solutions

Problem Overview: You are given the root of a binary tree and a target sum. The task is to determine whether the tree has a root-to-leaf path such that adding all node values along that path equals the target. A leaf means a node with no children. The main challenge is traversing the tree while continuously tracking the remaining sum.

Approach 1: Recursive Depth-First Search (DFS) (Time: O(n), Space: O(h))

The most natural way to solve this problem is recursion with Depth-First Search. Start at the root and subtract the current node's value from the target sum. Then recursively explore the left and right children with the updated remaining sum. If you reach a leaf node and the remaining sum equals that node's value, a valid path exists.

This works because DFS follows one path from root to leaf at a time, which matches the structure of the requirement. Each node is visited once, giving O(n) time where n is the number of nodes. The recursion stack stores the current path, leading to O(h) space where h is the height of the binary tree. This solution is clean, short, and widely used in interviews.

Approach 2: Iterative Depth-First Search with Stack (Time: O(n), Space: O(h))

If you want to avoid recursion, simulate DFS using an explicit stack. Store pairs of (node, remainingSum). Push the root with the initial target sum. On each iteration, pop a node, subtract its value, and check if it is a leaf with the correct remaining sum. If not, push its children onto the stack with the updated value.

This approach performs the same logical steps as recursive DFS but manages traversal manually. The stack ensures nodes are explored depth-first, just like recursion. Time complexity remains O(n) since each node is processed once. Space complexity is also O(h) because the stack holds at most the nodes along the current path. This method is useful in environments where recursion depth could be limited.

Both approaches rely on the properties of tree traversal. The key insight is that the running sum can be updated as you move down the tree instead of storing full paths.

Recommended for interviews: Recursive DFS is typically expected because it maps directly to the structure of the problem and produces concise code. Interviewers often want to see that you recognize root-to-leaf traversal as a DFS pattern. The iterative stack approach demonstrates deeper understanding of DFS mechanics and recursion elimination, which can be useful if the interviewer asks for an alternative implementation.