Does Any Root-to-Leaf Route Add Up to the Target

Easy15–20 min

Topics

Binary TreeDFSRecursionPath Sum

Companies

AmazonMicrosoftGoogleAdobe

You are given the root of a binary tree and an integer target. A route starts at the root, goes downward through children, and must end at a leaf (a node with no children). Return true if some route has node values that add up to exactly target, and false otherwise. An empty tree has no routes.

You can list the total of every route and check the list, or you can subtract each node's value from the target as you go down, so a leaf only needs to compare its own value with what remains.

Test Case 1:

Input:root = [6, 3, 8, 1, 4, null, 9, null, 2], target = 13

Output:true

Explanation:The route 6 → 3 → 4 ends at the leaf 4 and adds up to 6 + 3 + 4 = 13.

Test Case 2:

Input:root = [6, 3, 8, 1, 4, null, 9, null, 2], target = 10

Output:false

Explanation:The route 6 → 3 → 1 adds up to 10, but node 1 still has a child (2), so the route does not end at a leaf. The real leaf routes total 12, 13 and 23.

Test Case 3:

Input:root = [], target = 0

Output:false

Explanation:No nodes means no routes, even for a target of 0.

Constraints

◆0 ≤ number of nodes ≤ 100
◆−100 ≤ node.val ≤ 100; −1000 ≤ target ≤ 1000
◆The tree is given as its root node (null for an empty tree); each node has a val, a left child and a right child
◆A route starts at the root, moves downward and must END at a leaf (a node with no children). Return true if the values along at least one such route add up to exactly target; an empty tree has no route

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Collect Every Route Total, Then Look for the Target

Brute

Walk the whole tree once, carrying the running sum of the values on the way down. Each time a leaf is reached, append that route's total to a list. When the walk finishes, check whether the target appears in the list. It always visits every node (it cannot stop early even if the very first route already matches) and it stores one number per leaf, so time is O(n) and space is O(n) in the worst case.

TimeO(n)

SpaceO(n)

Java

Try it out

class Solution {
    public boolean routeAddsUp(TreeNode root, int target) {
        List<Integer> totals = new ArrayList<>();
        collect(root, 0, totals);
        return totals.contains(target);
    }

    private void collect(TreeNode node, int sum, List<Integer> totals) {
        if (node == null) return;
        sum += node.val;
        if (node.left == null && node.right == null) {
            totals.add(sum);
            return;
        }
        collect(node.left, sum, totals);
        collect(node.right, sum, totals);
    }
}

Optimal — Count Down the Remaining Amount and Stop Early

Optimal

Instead of adding up, subtract. Passing target − (this node's value) to the children means every child only has to find a route worth "what is still left". At a leaf the route is complete, so it succeeds exactly when the leaf's value equals the remaining amount. A missing child can never succeed. For an internal node, succeed if EITHER child does — and since || short-circuits, the search stops at the first successful route. Nothing is stored: O(h) space for the recursion, and O(n) time in the worst case (less when a route is found early).