Path Sum

Problem

Given a binary tree and a target sum, return true iff some root-to-leaf path sums to exactly target.

Constraints

• 0 ≤ nodes ≤ 5000
• −1000 ≤ Node.val ≤ 1000
• −1000 ≤ target ≤ 1000

Approach — Tree Traversal

This is a Tree Traversal problem. The idea: traverse the tree — DFS recursively, or BFS level by level — and combine the results from each subtree. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time.

Solution code

Python

class Solution:
    def hasPathSum(self, root, target):
        if not root:
            return False
        if not root.left and not root.right:
            return root.val == target
        rem = target - root.val
        return self.hasPathSum(root.left, rem) or self.hasPathSum(root.right, rem)

Java

class Solution {
    public boolean hasPathSum(TreeNode root, int target) {
        if (root == null) return false;
        if (root.left == null && root.right == null) return target == root.val;
        return hasPathSum(root.left, target - root.val)
            || hasPathSum(root.right, target - root.val);
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.