Problem Description
Given the root of a binary tree and an integer targetSum, determine if there is a root-to-leaf path in the tree such that the sum of the node values along the path equals targetSum. A leaf is defined as a node with no children.
Key Insights
- Use a depth-first search (DFS) strategy to traverse the tree from the root to the leaves.
- At each node, subtract the node’s value from the targetSum.
- Check if the node is a leaf; if yes and the remaining targetSum equals the node's value then a valid path is found.
- If the tree is empty, return false as no path exists.
Space and Time Complexity
Time Complexity: O(N) where N is the number of nodes, since every node may need to be visited. Space Complexity: O(H) where H is the height of the tree, accounting for the recursion stack (worst-case O(N) for a skewed tree).
Solution
The approach uses a recursive depth-first search. The algorithm subtracts the current node’s value from targetSum as it moves down the tree. When it reaches a leaf, it checks if the modified targetSum is equal to the leaf's value. If yes, it returns true. The recursion continues until either a valid path is found or all paths are exhausted. The primary data structure used here is the call stack for recursion.