Root-to-Leaf Target Path Sum: find if any path sums to a target

You're twenty minutes into your Google phone screen when the interviewer says, "I'm going to give you a binary tree and a number. Tell me if there's a path from the root to any leaf that adds up to that number." You nod, grab your virtual whiteboard, and start sketching a tree. This is Path Sum, one of the most common tree problems in technical interviews, and it tests your ability to combine recursive thinking with careful edge case handling.

TL;DR

Use depth-first search to traverse the tree, subtracting each node's value from the target sum as you go. When you reach a leaf node, check if its value equals the remaining target. If so, a valid path exists. This runs in O(n) time since every node may need to be visited, and uses O(h) space for the call stack where h is the tree height.

Why This Problem Matters

Path Sum sits at the intersection of two concepts interviewers love: binary tree traversal and recursive problem decomposition. It shows up frequently at Google, Bloomberg, Amazon, and Adobe, often as the opening question in a multi-part series. Solve this cleanly, and the interviewer will likely follow up with "now return all valid paths" (Path Sum II) or "what about paths that don't start at the root?" (Path Sum III). Getting the fundamentals right here sets you up for those harder variations.

Binary Trees: A Quick Refresher

A binary tree is a hierarchical data structure where each node has at most two children. Here is the example tree from our problem:

Key terminology:

• Root: The topmost node (5 in our example)
• Leaf: A node with no children (7, 2, 13, and 1 are all leaves)
• Path: A sequence of nodes from root to leaf, following parent-child connections
• Path sum: The total of all node values along a path

Understanding the Problem

Given a binary tree and an integer targetSum, determine whether any root-to-leaf path exists where the node values add up to targetSum.

For our example tree with targetSum = 22:

The path 5 -> 4 -> 11 -> 2 sums to 22, so the answer is true.

All root-to-leaf paths and their sums:

• 5 -> 4 -> 11 -> 7 = 27
• 5 -> 4 -> 11 -> 2 = 22 (match)
• 5 -> 8 -> 13 = 26
• 5 -> 8 -> 4 -> 1 = 18

Edge Cases to Consider

1. Empty tree (null root): No paths exist, return false
2. Single node: The node is both root and leaf; check if its value equals the target
3. Negative values: Node values can be negative, which is perfectly valid
4. No valid path: Every path may fall short or exceed the target

Solution Approach

The brute-force way to solve this would be to enumerate every root-to-leaf path, compute each sum, and check for a match. That works, but there is a cleaner technique.

The Subtraction Technique

Instead of accumulating a running sum and comparing it at the leaf, subtract each node's value from the target as you traverse downward. When you reach a leaf, you only need to check whether the leaf's value equals the remaining target.

For the path 5 -> 4 -> 11 -> 2 with targetSum = 22:

• At node 5: remaining = 22 - 5 = 17
• At node 4: remaining = 17 - 4 = 13
• At node 11: remaining = 13 - 11 = 2
• At node 2: this is a leaf, and 2 == 2, so return true

This works because the subtraction distributes the comparison across each level. At the leaf, the remaining value is targetSum - (sum of all ancestors), which equals the leaf's value only if the full path sums to the target.

Recursive Structure

The algorithm fits naturally into a recursive DFS:

1. Base case (null node): Return false. There is no path through a null node.
2. Leaf check: If the current node has no children, return whether its value equals the remaining target.
3. Recursive step: Subtract the current node's value from the target and recurse on both children. Return true if either subtree contains a valid path.

Tracing Through the Example

For our tree with targetSum = 22, here is how the recursion finds the valid path through the left subtree:

The recursion reaches leaf node 2 with a remaining target of 2. Since 2 == 2, it returns true, and that result propagates back up through the call chain.

Meanwhile, the right subtree path 5 -> 8 -> 13 fails:

Node 13 is a leaf, but 13 != 9, so this branch returns false. The algorithm continues checking other branches (the 4 -> 1 subtree), which also fails. Because the left subtree already found a valid path, the overall result is true.

Negative Values

The algorithm handles negative values without any special logic:

For targetSum = -5: remaining at node -2 is -5 - (-2) = -3. Node -3 is a leaf, and -3 == -3, so the answer is true.

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {

  public boolean hasPathSum(TreeNode root, int targetSum) {
    // Base case: null node means no path exists here
    if (root == null) {
      return false;
    }

    // Leaf node: check if this node's value matches the remaining target
    if (root.left == null && root.right == null) {
      return targetSum == root.data;
    }

    // Subtract current node's value and recurse on both children
    int newTargetSum = targetSum - root.data;
    return hasPathSum(root.left, newTargetSum) || hasPathSum(root.right, newTargetSum);
  }
}

Three things to note about this implementation:

1. The null check comes first. This handles both empty trees and the case where a node has only one child (the missing child is null).
2. The leaf check uses both root.left == null and root.right == null. A node with one child is not a leaf. Forgetting this check is the most common bug in Path Sum implementations.
3. Short-circuit evaluation. The || operator means if the left subtree returns true, the right subtree is never explored.

Complexity Analysis

Time Complexity: O(n)

Every node is visited at most once. In the worst case (no valid path exists), the algorithm explores the entire tree. Each visit performs constant work: one subtraction, one or two comparisons, and up to two recursive calls.

Space Complexity: O(h)

The space is determined by the maximum depth of the recursion stack, which equals the height h of the tree.

• Balanced tree: h = O(log n), so space is O(log n)
• Skewed tree (all nodes on one side): h = n, so space is O(n)

There is no auxiliary data structure, just the call stack.

Common Pitfalls

1. Checking sum at internal nodes instead of leaves. The problem requires root-to-leaf paths. If you return true when targetSum - root.data == 0 at a non-leaf node, you will produce false positives for trees where an internal node's running sum happens to match.

2. Treating a node with one child as a leaf. A node with a left child but no right child is not a leaf. The path must continue through its existing child.

3. Forgetting the empty tree case. If root is null, the answer is false, not true (even when targetSum is 0). An empty tree has no paths.

4. Ignoring negative values. Some candidates assume all values are positive and try to prune branches where the running sum exceeds the target. This optimization is invalid when nodes can have negative values.

Interview Tips

When you see this problem in an interview:

1. Clarify the definition of "leaf." Confirm that a leaf is a node with zero children. This prevents the most common bug.

2. Mention the subtraction technique up front. Saying "I'll subtract each node's value from the target as I go, so at the leaf I just compare" shows you have a plan before writing code.

3. Walk through one valid and one invalid path. Tracing 5 -> 4 -> 11 -> 2 (valid) and 5 -> 8 -> 13 (invalid) demonstrates correctness and catches logic errors.

4. Discuss the iterative alternative. Mentioning that you could use an explicit stack with (node, remaining) pairs shows breadth of knowledge. The recursive approach is cleaner for interviews, but knowing both is a plus.

5. Anticipate follow-ups. Be ready for "return all valid paths" (Path Sum II, uses backtracking) and "paths can start anywhere" (Path Sum III, uses prefix sums).

Key Takeaways

• Subtract the current node's value from the target at each step so the leaf check reduces to a single equality comparison.
• A leaf is a node where both left and right are null. Checking only one side causes false positives.
• The recursion short-circuits via ||. If the left subtree finds a valid path, the right subtree is skipped entirely.
• Time complexity is O(n) and space complexity is O(h), making this optimal for the problem constraints.
• This recursive DFS pattern (null check, leaf check, recurse on children) is the foundation for Path Sum II, Path Sum III, and many other tree traversal problems.

Solutions in Other Languages

Python

class Solution:
    def has_path_sum(self, root, target_sum):
        if not root:
            return False

        if not root.left and not root.right:
            return root.data == target_sum

        target_sum -= root.data
        return (self.has_path_sum(root.left, target_sum) or
                self.has_path_sum(root.right, target_sum))

JavaScript

class Solution {
  hasPathSum(root, targetSum) {
    if (!root) {
      return false;
    }

    if (!root.left && !root.right) {
      return targetSum === root.data;
    }

    const newTargetSum = targetSum - root.data;
    return this.hasPathSum(root.left, newTargetSum) || this.hasPathSum(root.right, newTargetSum);
  }
}

TypeScript

class Solution {
  hasPathSum(root: TreeNode | null, targetSum: number): boolean {
    if (root === null) return false;

    if (root.left === null && root.right === null) {
      return root.data === targetSum;
    }

    const newTargetSum = targetSum - root.data;
    return this.hasPathSum(root.left, newTargetSum) || this.hasPathSum(root.right, newTargetSum);
  }
}

C++

class Solution {
public:
  bool hasPathSum(TreeNode *root, int targetSum) {
    if (!root) {
      return false;
    }

    if (!root->left && !root->right) {
      return targetSum == root->data;
    }

    int newTargetSum = targetSum - root->data;
    return hasPathSum(root->left, newTargetSum) || hasPathSum(root->right, newTargetSum);
  }
};

Go

func (s *Solution) HasPathSum(root *TreeNode, targetSum int) bool {
    if root == nil {
        return false
    }

    if root.Left == nil && root.Right == nil {
        return root.Data == targetSum
    }

    remainingSum := targetSum - root.Data
    return s.HasPathSum(root.Left, remainingSum) || s.HasPathSum(root.Right, remainingSum)
}

Kotlin

fun hasPathSum(root: TreeNode?, targetSum: Int): Boolean {
    if (root == null) {
        return false
    }

    if (root.left == null && root.right == null) {
        return targetSum == root.data
    }

    val newTargetSum = targetSum - root.data
    return hasPathSum(root.left, newTargetSum) || hasPathSum(root.right, newTargetSum)
}

Scala

def hasPathSum(root: TreeNode, targetSum: Int): Boolean = {
    if (root == null) return false

    if (root.left == null && root.right == null) {
        return root.data == targetSum
    }

    val newTargetSum = targetSum - root.data
    hasPathSum(root.left, newTargetSum) || hasPathSum(root.right, newTargetSum)
}

Swift

func hasPathSum(_ root: TreeNode?, _ targetSum: Int) -> Bool {
    if root == nil {
        return false
    }

    if root!.left == nil && root!.right == nil {
        return targetSum == root!.data
    }

    let newTargetSum = targetSum - root!.data
    return hasPathSum(root!.left, newTargetSum) || hasPathSum(root!.right, newTargetSum)
}

Ruby

def has_path_sum?(root, target_sum)
    return false if root.nil?

    if root.left.nil? && root.right.nil?
        return target_sum == root.data
    end

    new_target_sum = target_sum - root.data
    has_path_sum?(root.left, new_target_sum) || has_path_sum?(root.right, new_target_sum)
end

Rust

The Rust version uses a helper function to work with references, avoiding ownership issues with Option<Box<TreeNode>>.

impl Solution {
    pub fn has_path_sum(&self, root: Option<Box<TreeNode>>, target_sum: i32) -> bool {
        Self::helper(&root, target_sum)
    }

    fn helper(node: &Option<Box<TreeNode>>, target_sum: i32) -> bool {
        if node.is_none() {
            return false;
        }

        let node = node.as_ref().unwrap();

        if node.left.is_none() && node.right.is_none() {
            return target_sum == node.data;
        }

        let new_target_sum = target_sum - node.data;
        Self::helper(&node.left, new_target_sum) || Self::helper(&node.right, new_target_sum)
    }
}

C#

public bool HasPathSum(TreeNode? root, int targetSum) {
    if (root == null) {
        return false;
    }

    if (root.left == null && root.right == null) {
        return targetSum == root.data;
    }

    int newTargetSum = targetSum - root.data;
    return HasPathSum(root.left, newTargetSum) || HasPathSum(root.right, newTargetSum);
}

Dart

bool hasPathSum(TreeNode? root, int targetSum) {
    if (root == null) {
        return false;
    }

    if (root.left == null && root.right == null) {
        return targetSum == root.data;
    }

    int newTargetSum = targetSum - root.data;
    return hasPathSum(root.left, newTargetSum) || hasPathSum(root.right, newTargetSum);
}

PHP

public function hasPathSum(?TreeNode $root, int $targetSum): bool {
    if ($root === null) {
        return false;
    }

    if ($root->left === null && $root->right === null) {
        return $targetSum === $root->data;
    }

    $newTargetSum = $targetSum - $root->data;
    return $this->hasPathSum($root->left, $newTargetSum) || $this->hasPathSum($root->right, $newTargetSum);
}

Related Problems

Once you are comfortable with Path Sum, try these to build on the same recursive DFS foundation:

• Path Sum II - return all valid root-to-leaf paths (adds backtracking)
• Path Sum III - paths can start at any node (uses prefix sums)
• Binary Tree Maximum Path Sum - maximum sum path across any two nodes (harder variation)
• Height of a Binary Tree - same recursive structure, simpler aggregation

This problem and hundreds of others are available on Firecode, where over 50,000 engineers have prepared for technical interviews and landed roles at top companies. Consistent practice with problems like Path Sum builds the recursive thinking skills that interviews demand.