Path Sum solution and explanation
Google
9 more videos on this problem
Path Sum - Leetcode 112 - PythonNeetCode · 6:43 · 97K views
LeetCode Path Sum Solution Explained - JavaNick White · 7:19 · 38K views
Path Sum (LeetCode 112) | Full solution with visuals and graphics | Study AlgorithmsNikhil Lohia · 15:01 · 24K views
Path Sum - Leetcode 112 - Trees (Python)Greg Hogg · 4:24 · 10K views
LeetCode 112: Path SumEngineering Digest · 6:29 · 4K views
Leetcode 112: Path Sum - Best Explanation with Code!CodingNinja · 4:09 · 3K views
[Java] Leetcode 112. Path Sum [Binary Tree #12]Eric Programming · 7:02 · 2K views
LeetCode 112: Path Sum | C++Blake Wright · 6:37 · 2K views
LeetCode 112 | Path Sum | Solution Explained | Java + WhiteboardXavier Elon · 8:11 · 1K views
Path Sum - LeetCode 112 - JavaScriptAlgoJS · 6:27 · 1K views
The problem
Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.
A leaf is a node with no children.
Example 1:
Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 Output: true Explanation: The root-to-leaf path with the target sum is shown.
Example 2:
Input: root = [1,2,3], targetSum = 5 Output: false Explanation: There are two root-to-leaf paths in the tree: (1 --> 2): The sum is 3. (1 --> 3): The sum is 4. There is no root-to-leaf path with sum = 5.
Example 3:
Input: root = [], targetSum = 0 Output: false Explanation: Since the tree is empty, there are no root-to-leaf paths.
Constraints:
- The number of nodes in the tree is in the range
[0, 5000]. -1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
Approach overview
Problem Overview: Given the root of a binary tree and an integer targetSum, determine whether the tree has a root‑to‑leaf path where the sum of node values equals the target. A valid path must start at the root and end at a leaf node.
Approach 1: Recursive Depth-First Search (DFS) (Time: O(n), Space: O(h))
The recursive DFS approach walks down the tree while subtracting the current node’s value from targetSum. Each recursive call moves to either the left or right child with the updated remaining sum. When you reach a leaf node (both children are null), check whether the remaining sum equals the node’s value. If it does, a valid root-to-leaf path exists. This method naturally fits recursive traversal of a tree and keeps the implementation clean because the call stack tracks the current path automatically. Time complexity is O(n) since every node may be visited once. Space complexity is O(h), where h is the height of the tree, due to recursion stack usage.
Approach 2: Iterative Depth-First Search with Stack (Time: O(n), Space: O(h))
An iterative version replaces recursion with an explicit stack. Each stack entry stores a node and the remaining sum required for that path. Start by pushing the root and the original target sum. During traversal, pop the top node, subtract its value from the remaining sum, and check if it is a leaf node with the correct total. If not, push its children onto the stack with the updated remaining sum. This approach mirrors recursive depth-first search but gives you direct control over traversal and avoids recursion limits. Time complexity remains O(n) because each node is processed once. Space complexity is O(h) in the average case, corresponding to the maximum stack depth in a binary tree.
Recommended for interviews: The recursive DFS solution is what most interviewers expect first. It clearly shows that you understand root-to-leaf traversal and how to propagate state (the remaining sum) through recursion. After presenting the recursive version, mentioning the iterative stack-based DFS demonstrates deeper knowledge of traversal mechanics and how recursion can be simulated with an explicit stack.
Approach 1: Recursive Depth-First Search (DFS)
This approach uses a recursive DFS strategy to navigate from the root to each leaf, calculating the cumulative sum along the path. If we find a path where the cumulative sum equals the targetSum at a leaf node, we return true. Otherwise, we continue exploring other paths. In case we exhaust all paths without finding a valid path, we return false.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def hasPathSum(root, targetSum):
if not root:
return False
if not root.left and not root.right:
return root.val == targetSum
targetSum -= root.val
return hasPathSum(root.left, targetSum) or hasPathSum(root.right, targetSum)class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) { this.val = val; }
}
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) return false;
if (root.left == null && root.right == null) return root.val == targetSum;
targetSum -= root.val;
return hasPathSum(root.left, targetSum) || hasPathSum(root.right, targetSum);
}
}struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
bool hasPathSum(TreeNode* root, int targetSum) {
if (!root) return false;
if (!root->left && !root->right) return root->val == targetSum;
targetSum -= root->val;
return hasPathSum(root->left, targetSum) || hasPathSum(root->right, targetSum);
}
};function TreeNode(val, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
var hasPathSum = function(root, targetSum) {
if (!root) return false;
if (!root.left && !root.right) return root.val === targetSum;
targetSum -= root.val;
return hasPathSum(root.left, targetSum) || hasPathSum(root.right, targetSum);
};#include <stdbool.h>
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
bool hasPathSum(TreeNode* root, int targetSum) {
if (!root) return false;
if (!root->left && !root->right) return root->val == targetSum;
targetSum -= root->val;
return hasPathSum(root->left, targetSum) || hasPathSum(root->right, targetSum);
}public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public bool HasPathSum(TreeNode root, int targetSum) {
if (root == null) return false;
if (root.left == null && root.right == null) return root.val == targetSum;
targetSum -= root.val;
return HasPathSum(root.left, targetSum) || HasPathSum(root.right, targetSum);
}
}In this Python solution, we define a recursive function hasPathSum that deducts the current node's value from targetSum as we traverse the tree. If we reach a leaf node (both children are None) and the remaining targetSum equals the leaf node's value, we return true; otherwise, false. The recursion continues for left and right subtrees.
Time Complexity: O(N), where N is the number of nodes in the tree, as we have to visit each node.
Space Complexity: O(H), where H is the height of the tree due to the recursion stack.
Approach 2: Iterative Depth-First Search with Stack
In contrast to the recursive method, this approach utilizes an explicit stack to iteratively perform DFS, tracking the cumulative sum along each path. Nodes are pushed onto the stack with their cumulative sums traversed thus far, effectively replacing the recursion stack with an explicit stack to manage state manually. This can help in environments with limited recursion support.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def hasPathSum(root, targetSum):
if not root:
return False
stack = [(root, root.val)]
while stack:
node, currSum = stack.pop()
if not node.left and not node.right and currSum == targetSum:
return True
if node.right:
stack.append((node.right, currSum + node.right.val))
if node.left:
stack.append((node.left, currSum + node.left.val))
return Falseimport java.util.Stack;
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) return false;
Stack<TreeNode> nodes = new Stack<>();
Stack<Integer> sums = new Stack<>();
nodes.push(root);
sums.push(root.val);
while (!nodes.isEmpty()) {
TreeNode current = nodes.pop();
int currentSum = sums.pop();
if (current.left == null && current.right == null && currentSum == targetSum) {
return true;
}
if (current.right != null) {
nodes.push(current.right);
sums.push(currentSum + current.right.val);
}
if (current.left != null) {
nodes.push(current.left);
sums.push(currentSum + current.left.val);
}
}
return false;
}
}#include <stack>
class Solution {
public:
bool hasPathSum(TreeNode* root, int targetSum) {
if (!root) return false;
std::stack<TreeNode*> nodes;
std::stack<int> sums;
nodes.push(root);
sums.push(root->val);
while (!nodes.empty()) {
TreeNode* currentNode = nodes.top(); nodes.pop();
int currentSum = sums.top(); sums.pop();
if (!currentNode->left && !currentNode->right && currentSum == targetSum) {
return true;
}
if (currentNode->right) {
nodes.push(currentNode->right);
sums.push(currentSum + currentNode->right->val);
}
if (currentNode->left) {
nodes.push(currentNode->left);
sums.push(currentSum + currentNode->left->val);
}
}
return false;
}
};function TreeNode(val, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
var hasPathSum = function(root, targetSum) {
if (!root) return false;
const stack = [{ node: root, currSum: root.val }];
while (stack.length > 0) {
const { node, currSum } = stack.pop();
if (!node.left && !node.right && currSum === targetSum) {
return true;
}
if (node.right) {
stack.push({ node: node.right, currSum: currSum + node.right.val });
}
if (node.left) {
stack.push({ node: node.left, currSum: currSum + node.left.val });
}
}
return false;
};#include <stdbool.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
typedef struct StackNode {
TreeNode* treeNode;
int currentSum;
struct StackNode* next;
} StackNode;
void push(StackNode** stack, TreeNode* treeNode, int currentSum) {
StackNode* newNode = (StackNode*)malloc(sizeof(StackNode));
newNode->treeNode = treeNode;
newNode->currentSum = currentSum;
newNode->next = *stack;
*stack = newNode;
}
void pop(StackNode** stack) {
StackNode* temp = *stack;
*stack = (*stack)->next;
free(temp);
}
bool hasPathSum(TreeNode* root, int targetSum) {
if (!root) return false;
StackNode* stack = NULL;
push(&stack, root, root->val);
while (stack != NULL) {
TreeNode* currentNode = stack->treeNode;
int currSum = stack->currentSum;
pop(&stack);
if (!currentNode->left && !currentNode->right && currSum == targetSum) {
return true;
}
if (currentNode->right) {
push(&stack, currentNode->right, currSum + currentNode->right->val);
}
if (currentNode->left) {
push(&stack, currentNode->left, currSum + currentNode->left->val);
}
}
return false;
}using System.Collections.Generic;
public class Solution {
public bool HasPathSum(TreeNode root, int targetSum) {
if (root == null) return false;
Stack<TreeNode> stack = new Stack<TreeNode>();
Stack<int> sums = new Stack<int>();
stack.Push(root);
sums.Push(root.val);
while (stack.Count > 0) {
TreeNode currentNode = stack.Pop();
int currSum = sums.Pop();
if (currentNode.left == null && currentNode.right == null && currSum == targetSum) {
return true;
}
if (currentNode.right != null) {
stack.Push(currentNode.right);
sums.Push(currSum + currentNode.right.val);
}
if (currentNode.left != null) {
stack.Push(currentNode.left);
sums.Push(currSum + currentNode.left.val);
}
}
return false;
}
}The Python solution leverages a stack to simulate DFS. When visiting a node, the accumulated sum of the path is tracked, ensuring each leaf node is evaluated against targetSum. Left and right children are pushed onto the stack with updated path sums.
Time Complexity: O(N), examining each node iteratively.
Space Complexity: O(N), as the stack could store up to all nodes in the worst scenario (e.g., a path-heavy tree with a single path).
Approach 3: Recursion
Starting from the root node, recursively traverse the tree and update the value of the node to the path sum from the root node to that node. When you traverse to a leaf node, determine whether this path sum is equal to the target value. If it is equal, return true, otherwise return false.
The time complexity is O(n), where n is the number of nodes in the binary tree. Each node is visited once.
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function hasPathSum(root: TreeNode | null, targetSum: number): boolean {
if (root === null) {
return false;
}
const { val, left, right } = root;
if (left === null && right === null) {
return targetSum - val === 0;
}
return hasPathSum(left, targetSum - val) || hasPathSum(right, targetSum - val);
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func hasPathSum(root *TreeNode, targetSum int) bool {
var dfs func(*TreeNode, int) bool
dfs = func(root *TreeNode, s int) bool {
if root == nil {
return false
}
s += root.Val
if root.Left == nil && root.Right == nil && s == targetSum {
return true
}
return dfs(root.Left, s) || dfs(root.Right, s)
}
return dfs(root, 0)
}// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
pub fn has_path_sum(root: Option<Rc<RefCell<TreeNode>>>, target_sum: i32) -> bool {
match root {
None => false,
Some(node) => {
let mut node = node.borrow_mut();
// 确定叶结点身份
if node.left.is_none() && node.right.is_none() {
return target_sum - node.val == 0;
}
let val = node.val;
Self::has_path_sum(node.left.take(), target_sum - val)
|| Self::has_path_sum(node.right.take(), target_sum - val)
}
}
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Recursive Depth-First Search (DFS) | Time Complexity: O(N), where N is the number of nodes in the tree, as we have to visit each node. |
| Iterative Depth-First Search with Stack | Time Complexity: O(N), examining each node iteratively. |
| Recursion | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Depth-First Search (DFS) | O(n) | O(h) | Cleanest implementation for tree traversal; ideal for interviews and typical binary tree recursion problems. |
| Iterative DFS with Stack | O(n) | O(h) | Useful when avoiding recursion limits or when you want explicit control over traversal order. |
Frequently asked questions
Is Path Sum easy or hard?
Path Sum is categorized as an Easy problem on LeetCode with an acceptance rate around 54%. The main challenge is recognizing that the path must end at a leaf node and correctly updating the remaining target during traversal.
How to solve Path Sum in O(n)?
Use depth-first traversal while carrying the remaining sum needed to reach the target. At each node, subtract the node value from the target and continue exploring its children. If a leaf node is reached and the remaining sum equals its value, a valid path exists. Each node is visited once, resulting in O(n) time complexity.
What is the best approach for Path Sum?
Depth-First Search (DFS) is the most efficient and commonly used approach. Traverse the tree from root to leaf while subtracting node values from the target sum. When a leaf node is reached, check whether the remaining sum equals the node value. This solution runs in O(n) time and O(h) space, where h is the tree height.
What data structure is used in Path Sum?
The problem uses a binary tree as the primary data structure. Solutions typically rely on depth-first traversal, implemented either with recursion (call stack) or an explicit stack. Some variations can also be solved with breadth-first search using a queue.
What is the time complexity of Path Sum?
The time complexity is O(n) because every node in the binary tree may be visited once during traversal. Both recursive DFS and iterative DFS implementations process each node a single time. Space complexity is O(h), which represents the maximum recursion depth or stack size based on the tree height.
Path Sum Python or Java solution approach?
Both Python and Java implementations follow the same DFS idea. The recursive solution passes the remaining sum down the tree and checks the condition at leaf nodes. Iterative versions use a stack storing pairs of (node, remainingSum) to simulate recursion while maintaining O(n) time complexity.
Is Path Sum asked at Google, Amazon, or Meta?
Path Sum and similar tree traversal problems frequently appear in interviews at companies like Amazon, Google, Meta, and Microsoft. They test understanding of binary tree traversal, recursion, and state propagation along a path. Variants such as Path Sum II and Path Sum III are also common interview follow-ups.