Skip to main content
Talentd

Path Sum - Solution & Explanation

EasyTreeDepth-First SearchBreadth-First SearchBinary Tree19 min readAsked at: Amazon, Microsoft, Apple +6
Practice this problem

Problem Statement

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.

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.

Code

PythonJavaC++CC#JavaScript

Python

Java

C++

C

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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.

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.

Code

PythonJavaC++CC#JavaScript

Python

Java

C++

C

C#

JavaScript

Complexity

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).

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(H), where H is the height of the tree due to the recursion stack.

Iterative Depth-First Search with Stack

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).

Recursion—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 StackO(n)O(h)Useful when avoiding recursion limits or when you want explicit control over traversal order.

Video Solution

Path Sum - Leetcode 112 - Python • NeetCode • 97,369 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Path Sum with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Tree Maximum Path Sum

Next

Path Sum II