Path Sum in a Binary Tree

Given a binary tree and a target sum, return true if the tree has a root-to-leaf path whose values add up to sum. A leaf is a node with no children.

LeetCode: 112. Path Sum

Example

graph TB
    a["5"] --> b["4"]
    a --> c["8"]
    b --> d["11"]
    c --> e["13"]
    c --> f["4"]
    d --> g["7"]
    d --> h["2"]
    f --> i["1"]

Text

sum = 22  ->  true    (5 + 4 + 11 + 2)
sum = 26  ->  true    (5 + 8 + 13)
sum = 9   ->  false   (5 + 4 stops at 4, which isn't a leaf)

Brute force: collect every path sum

Walk every root-to-leaf path, record its sum, and then look for the target. A tree node here is an object with left and right references. An empty subtree is null, so no wrapper type is needed.

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static class TreeNode {
        int val;
        TreeNode left, right;

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    static TreeNode leaf(int val) {
        return new TreeNode(val, null, null);
    }

    static void collectSums(TreeNode root, int soFar, List<Integer> sums) {
        if (root == null) return;
        int total = soFar + root.val;
        if (root.left == null && root.right == null) {
            sums.add(total);
        }
        collectSums(root.left, total, sums);
        collectSums(root.right, total, sums);
    }

    static boolean hasPathSum(TreeNode root, int sum) {
        List<Integer> sums = new ArrayList<>();
        collectSums(root, 0, sums);
        return sums.contains(sum);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5,
            new TreeNode(4, new TreeNode(11, leaf(7), leaf(2)), null),
            new TreeNode(8, leaf(13), new TreeNode(4, null, leaf(1))));
        System.out.println(hasPathSum(root, 22) + " " + hasPathSum(root, 26) + " " + hasPathSum(root, 9));
    }
}

Output

true true false

Time: O(n). Space: O(n): one sum per leaf, plus the recursion. It always visits the whole tree.

Optimal: subtract on the way down

Pass down the sum that is still needed. At a leaf, the path works if what remains equals the leaf's value. || stops the search as soon as one path matches.

Java

public class Main {
    static class TreeNode {
        int val;
        TreeNode left, right;

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    static TreeNode leaf(int val) {
        return new TreeNode(val, null, null);
    }

    static boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) return false;
        int remaining = sum - root.val;
        if (root.left == null && root.right == null) {
            return remaining == 0;
        }
        return hasPathSum(root.left, remaining) || hasPathSum(root.right, remaining);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5,
            new TreeNode(4, new TreeNode(11, leaf(7), leaf(2)), null),
            new TreeNode(8, leaf(13), new TreeNode(4, null, leaf(1))));
        System.out.println(hasPathSum(root, 22) + " " + hasPathSum(root, 26) + " " + hasPathSum(root, 9));
        System.out.println(hasPathSum(null, 0) + " " + hasPathSum(leaf(-3), -3));
    }
}

Output

true true false
false true

Time: O(n) in the worst case, less when a match is found early. Space: O(h) for the recursion. sum - root.val is int arithmetic and wraps on overflow; use long if values and targets can approach Integer.MAX_VALUE.

Edge cases

Empty tree: false, even for sum = 0, because there is no path.
Node with one child: not a leaf, so a path can't end there. That's why sum = 9 is false above.
Negative values: fine; there's no pruning based on the sum getting too large.