DSA · Trees · #135

Path Sum

Module 44 · difficulty 2/5·⏱ 30:00starts on first keystroke

Given the `root` of a binary tree and an integer `targetSum`, return `true` if the tree has a **root-to-leaf** path such that adding up all the values along the path equals `targetSum`, otherwise return `false`. A **leaf** is a node with no children. Implement the function `hasPathSum(root, targetSum)`. Each node is `{ val, left, right }`; an empty tree is `null`.

Examples

root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 → true — The path 5 -> 4 -> 11 -> 2 sums to 22.
root = [1,2,3], targetSum = 5 → false — Root-to-leaf paths are 1->2 (sum 3) and 1->3 (sum 4); neither equals 5.
root = [], targetSum = 0 → false — An empty tree has no root-to-leaf path.

Constraints

· The number of nodes is in the range [0, 5000].
· -1000 <= Node.val <= 1000
· -1000 <= targetSum <= 1000

Session phases

A · Clarify

B · Approach

C · Complexity

D · Edges

E · Code

F · Tradeoff

G · Score

Phase A — Clarify

Ask questions about input bounds, types, and edge constraints.

Ask the coach clarifying questions about the problem.

When you've covered this phase, advance to the next.