Definition
- Tree DFS pattern – recursively walk from root to each leaf, tracking the running target.
- Subtract as you go – at each node, subtract the node's value from the remaining target.
- Leaf test – success occurs only at a true leaf (both children null) where the remaining target equals zero.
- Short-circuit – combine left and right results with logical OR; the search stops at the first valid path.
- Complexity – O(n) time (visits each node once), O(h) space for the recursion stack.
At the National Bank of India, Rajesh submits a request that flows down a chain of approval desks. Each desk charges a processing fee. The budget is the target sum, and you need to know if any complete top-to-bottom chain of fees adds up to exactly the budget. You follow one chain all the way down, subtracting each fee, and check if the budget hits zero at the final desk.
Understanding the Concepts
What is the Binary Tree Path Sum problem?
Given a binary tree and an integer target sum, determine whether the tree has any root-to-leaf path whose node values sum to exactly the target. Return true if such a path exists, false otherwise.
A root-to-leaf path starts at the root and ends at a leaf (a node with no children). Every node on the path contributes its value to the sum.
Why is DFS the natural fit?
DFS naturally follows one root-to-leaf path at a time, which is exactly what we need: walk down a path, track the running sum, check at the leaf, and backtrack to try other paths. The recursion stack automatically handles the backtracking.
package com.bank.service;
import java.math.BigDecimal;
public class ApprovalBudgetChecker {
static class ApprovalDesk {
BigDecimal fee;
ApprovalDesk left, right;
ApprovalDesk(BigDecimal fee) { this.fee = fee; }
}
public static boolean hasPathSum(ApprovalDesk node, BigDecimal target) {
if (node == null) return false;
BigDecimal remaining = target.subtract(node.fee);
// Leaf test: both children null
if (node.left == null && node.right == null) {
return remaining.compareTo(BigDecimal.ZERO) == 0;
}
// Recurse into children with logical OR
return hasPathSum(node.left, remaining) || hasPathSum(node.right, remaining);
}
public static void main(String[] args) {
// 500
// / \
// 200 300
// / \
// 100 150
ApprovalDesk root = new ApprovalDesk(new BigDecimal("500"));
root.left = new ApprovalDesk(new BigDecimal("200"));
root.right = new ApprovalDesk(new BigDecimal("300"));
root.left.left = new ApprovalDesk(new BigDecimal("100"));
root.left.right = new ApprovalDesk(new BigDecimal("150"));
BigDecimal budget = new BigDecimal("800");
System.out.println("Path sum " + budget + ": " + hasPathSum(root, budget));
// Path: 500 -> 200 -> 100 = 800? Yes!
BigDecimal budget2 = new BigDecimal("850");
System.out.println("Path sum " + budget2 + ": " + hasPathSum(root, budget2));
// Path: 500 -> 200 -> 150 = 850? Yes!
BigDecimal budget3 = new BigDecimal("900");
System.out.println("Path sum " + budget3 + ": " + hasPathSum(root, budget3));
// No path sums to 900
}
}
Path sum 800: true
Path sum 850: true
Path sum 900: false
Why must you check for a leaf, not for null?
The leaf test is the most important correctness detail. You must only declare success at a true leaf where both children are null, never at a null child. If you check at null, a path that merely passes through a node whose value equals the remaining target would falsely succeed before the path actually ends.
// WRONG: checking at null
public static boolean hasPathSumBuggy(ApprovalDesk node, BigDecimal target) {
if (node == null) return target.compareTo(BigDecimal.ZERO) == 0;
// BUG: for a node with only a left child, the null right child
// might return true if the remaining target happens to be 0,
// even though the path hasn't reached a real leaf.
return hasPathSumBuggy(node.left, target.subtract(node.fee))
|| hasPathSumBuggy(node.right, target.subtract(node.fee));
}
// CORRECT: checking at leaf
public static boolean hasPathSumCorrect(ApprovalDesk node, BigDecimal target) {
if (node == null) return false;
BigDecimal remaining = target.subtract(node.fee);
if (node.left == null && node.right == null) {
return remaining.compareTo(BigDecimal.ZERO) == 0;
}
return hasPathSumCorrect(node.left, remaining)
|| hasPathSumCorrect(node.right, remaining);
}
How does the iterative DFS version work?
Use an explicit stack of pairs (node, remaining target) to simulate the recursion.
import java.util.Stack;
public static boolean hasPathSumIterative(ApprovalDesk root, BigDecimal target) {
if (root == null) return false;
Stack<Object[]> stack = new Stack<>();
stack.push(new Object[]{root, target.subtract(root.fee)});
while (!stack.isEmpty()) {
Object[] pair = stack.pop();
ApprovalDesk node = (ApprovalDesk) pair[0];
BigDecimal remaining = (BigDecimal) pair[1];
if (node.left == null && node.right == null
&& remaining.compareTo(BigDecimal.ZERO) == 0) {
return true;
}
if (node.right != null) {
stack.push(new Object[]{node.right, remaining.subtract(node.right.fee)});
}
if (node.left != null) {
stack.push(new Object[]{node.left, remaining.subtract(node.left.fee)});
}
}
return false;
}
How is this related to other path sum variants?
| Variant | Description | Approach |
|---|---|---|
| Path Sum I (this) | Does any root-to-leaf path equal target? | DFS, return boolean |
| Path Sum II | Find all root-to-leaf paths equalling target | DFS + backtracking, collect paths |
| Path Sum III | Count paths starting at any node | Prefix sum + hashmap |
| Max Path Sum | Maximum sum path between any two nodes | DFS with global max |
// Path Sum II: collect all valid paths
public static List<List<BigDecimal>> findAllPaths(
ApprovalDesk node, BigDecimal target, List<BigDecimal> currentPath) {
List<List<BigDecimal>> result = new ArrayList<>();
if (node == null) return result;
currentPath.add(node.fee);
BigDecimal remaining = target.subtract(node.fee);
if (node.left == null && node.right == null
&& remaining.compareTo(BigDecimal.ZERO) == 0) {
result.add(new ArrayList<>(currentPath));
}
result.addAll(findAllPaths(node.left, remaining, currentPath));
result.addAll(findAllPaths(node.right, remaining, currentPath));
currentPath.remove(currentPath.size() - 1); // backtrack
return result;
}
What about negative node values?
When node values can be negative, you cannot prune a branch early just because the remaining target went negative. A negative node deeper in the tree could bring the sum back to the target. You must always reach a leaf to decide.
// With negative values: cannot prune early
// 5
// / \
// -3 2
// /
// 4
// Target: 6. Path: 5 -> -3 -> 4 = 6. Remaining goes negative then positive.
What are the edge cases?
- Null root – return false.
- Single node (leaf) – return whether its value equals the target.
- Target is zero with non-zero nodes – must still walk to leaves; intermediate zeros do not count.
- All negative values – negative target might have a valid path.
// Edge case: single node
ApprovalDesk single = new ApprovalDesk(new BigDecimal("42"));
System.out.println(hasPathSum(single, new BigDecimal("42"))); // true
System.out.println(hasPathSum(single, new BigDecimal("0"))); // false
What are common mistakes?
Besides the null-vs-leaf bug, the most common mistake is using == instead of .compareTo() for BigDecimal comparison.
// WRONG: == compares object references
if (remaining == BigDecimal.ZERO) // always false for new BigDecimal
// CORRECT: use compareTo
if (remaining.compareTo(BigDecimal.ZERO) == 0)
What is the time and space complexity?
Time is O(n) because each node is visited at most once. Space is O(h) for the recursion stack, where h is the height of the tree. The logical OR short-circuits: once a valid path is found, the right subtree is not explored, but the worst case visits all nodes.
What should a senior engineer know?
A senior engineer should recognise Path Sum as the simplest instance of the Tree Depth First Search pattern. The subtraction approach (passing target - node.value down) is cleaner than passing an accumulating sum, because it avoids a separate base-case comparison.
They should also know Path Sum III (count paths from any node) which requires prefix sums with a hashmap for O(n) time, and Max Path Sum which requires tracking global maximums through DFS. Understanding the full Path Sum family shows depth in tree DFS.
Visual Overview
Tree: Target = 800
500
/ \
200 300
/ \
100 150
DFS Trace (subtract as you go):
┌──────────────────────────────────────────────┐
│ hasPathSum(500, 800) │
│ remaining = 800 - 500 = 300 │
│ Not a leaf, recurse: │
│ │
│ hasPathSum(200, 300) │
│ remaining = 300 - 200 = 100 │
│ Not a leaf, recurse: │
│ │
│ hasPathSum(100, 100) │
│ remaining = 100 - 100 = 0 │
│ LEAF! remaining == 0 -> return TRUE │
│ │
│ Left child returned true, short-circuit │
│ (right child 300 not explored) │
└──────────────────────────────────────────────┘
Leaf Test (correctness):
┌──────────────────────────────────────────────┐
│ A LEAF has both children null. │
│ A NULL child is NOT a leaf. │
│ Check at leaf, not at null, to avoid │
│ false positives from single-child nodes. │
└──────────────────────────────────────────────┘
Key Takeaway
Binary Tree Path Sum is the classic Tree Depth First Search problem. You walk from the root to each leaf, subtracting each node's value from the running target. At a leaf, you check whether the remaining target is exactly zero. For non-leaf nodes, you combine the left and right results with logical OR, short-circuiting as soon as one valid path is found.
The most important correctness detail is the leaf test. You only declare success at a true leaf where both children are null, never at a null child. Checking at null creates false positives when a single-child node's missing child happens to make the remaining target zero. This is the bug interviewers are watching for.
At the National Bank of India, Rajesh used this pattern to validate approval fee chains. A transfer request flowed through a tree of approval desks, each charging a BigDecimal fee, and compliance needed to confirm that at least one complete chain carried fees summing to exactly the budgeted amount. Using BigDecimal's compareTo for the zero check ensured money-safe comparison.
The senior depth comes from knowing the Path Sum family: Path Sum I (this problem), Path Sum II (collect all valid paths via backtracking), Path Sum III (count paths from any node using prefix sums), and Max Path Sum (global maximum with DFS). Understanding the full family shows mastery of tree DFS.
Remember one sentence: Subtract each node's value from the target as you descend, and declare success only at a true leaf where the remaining target hits exactly zero.
---