What is the time complexity of Path Sum?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Path Sum?

This problem uses Tree, Depth-First Search, Breadth-First Search, Binary Tree. Understanding these concepts is essential for solving this Easy problem efficiently.

What are the key insights for solving Path Sum?

**Leaf-Node Specific Sum Check:** The `targetSum` comparison is strictly performed *only* when a `node` is confirmed to be a leaf (`not node.left and not node.right`). This precisely adheres to the 'root-to-leaf' requirement and distinguishes it from problems asking for path sums ending at any arbitrary node. **Cumulative Sum through Recursion State:** The `current_sum` isn't a global variable. Instead, it's passed as an argument in each recursive call. This elegant pattern ensures that each branch of the DFS independently maintains its path's sum, naturally 'undoing' parent sums as the call stack unwinds and preventing interference between sibling paths.

Which companies ask LeetCode 112. Path Sum in interviews?

This problem is frequently asked at Datadog, PayPal, TikTok.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Path Sum - LeetCode 112 Solution

Path Sum - Complete Solution Guide

Path Sum is LeetCode problem 112, a Easy level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

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

Detailed Explanation

You're handed the root of a binary tree and a specific `targetSum`. Your mission isn't just to find any path that adds up to this sum, but very specifically, a 'root-to-leaf' path. This means starting at the very top of the tree, traversing downwards, and only checking the sum once you've arrived at a node that has no children whatsoever (a true 'leaf'). If even one such path exists, you return `true`; otherwise, `false`.

Solution Approach

The provided solution leverages a classic Depth-First Search (DFS) strategy, which is perfectly suited for exploring every possible root-to-leaf path. It's a recursive journey: we start at the root and pass down the `current_sum` accumulated so far. At each node, we add the node's value to our `current_sum`. The key logic then splits: if we've arrived at a leaf node (meaning it has no left *and* no right child), we check if our `current_sum` now equals the `targetSum`. If it does, we've found our path, and we can immediately return `true`. If it's not a leaf, we continue the journey by recursively calling our `dfs` function on both the left and right children. The `or` operator here is crucial – if *either* the left branch *or* the right branch eventually finds a path, our overall `hasPathSum` function correctly returns `true`, short-circuiting any further exploration.

Step-by-Step Algorithm

Step 1: Check if the root node is null. If it is, return `false` because there are no paths.
Step 2: If the current node is a leaf node (no left and no right children), check if the current sum (accumulated during the traversal) equals the `targetSum`. Return `true` if they are equal, `false` otherwise.
Step 3: Recursively call the function (DFS) for the left and right subtrees. Subtract the current node's value from the `targetSum` before the recursive call. Return `true` if either recursive call returns `true`, indicating a path with the target sum was found; otherwise, return `false`.

Key Insights

**Leaf-Node Specific Sum Check:** The `targetSum` comparison is strictly performed *only* when a `node` is confirmed to be a leaf (`not node.left and not node.right`). This precisely adheres to the 'root-to-leaf' requirement and distinguishes it from problems asking for path sums ending at any arbitrary node.
**Cumulative Sum through Recursion State:** The `current_sum` isn't a global variable. Instead, it's passed as an argument in each recursive call. This elegant pattern ensures that each branch of the DFS independently maintains its path's sum, naturally 'undoing' parent sums as the call stack unwinds and preventing interference between sibling paths.
**Early Exit with Logical `or`:** The `dfs(node.left, current_sum) or dfs(node.right, current_sum)` structure provides an efficient short-circuiting mechanism. As soon as *any* left or right branch finds a valid path summing to `targetSum`, the `or` condition evaluates to `true`, and subsequent explorations (e.g., of the right subtree if the left finds a path) are completely bypassed, optimizing execution time.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(h)

Topics

This problem involves: Tree, Depth-First Search, Breadth-First Search, Binary Tree.

Companies

Asked at: Datadog, PayPal, TikTok.

Path Sum | LeetCode 112

Easy

Tree Depth-First Search Breadth-First Search Binary Tree

Time: O(n)Space: O(h)

Solution Code

Available in:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }

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

        return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 112: Path Sum - Detailed explanation and solution approaches.

Topics

Tree Depth-First Search Breadth-First Search Binary Tree

Companies

DatadogPayPalTikTok

Stats

Difficulty:Easy

Languages:4

Companies:3

Problem #:112

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

3 steps

1
Step 1: Check if the root node is null. If it is, return `false` because there are no paths.
2
Step 2: If the current node is a leaf node (no left and no right children), check if the current sum (accumulated during the traversal) equals the `targetSum`. Return `true` if they are equal, `false` otherwise.
3
Step 3: Recursively call the function (DFS) for the left and right subtrees. Subtract the current node's value from the `targetSum` before the recursive call. Return `true` if either recursive call returns `true`, indicating a path with the target sum was found; otherwise, return `false`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(h)

📝

Why?

The time complexity is O(n) because in the worst case, we visit each node in the tree once. The space complexity is O(h), where h is the height of the tree, because of the recursive call stack. In the worst case (a skewed tree), the height can be equal to n (the number of nodes). In a balanced tree, h is log(n).

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Iterative DFS using Stack

Instead of recursion, we can use an iterative approach with a stack to simulate the recursive calls. This can avoid potential stack overflow errors for very deep trees.

Time: O(n)Space: O(h)

Trade-offs: The iterative approach might be slightly less elegant than the recursive one, but it can be more robust for extremely deep trees. It trades readability for potential robustness

Breadth-First Search (BFS)

BFS can also be used to solve this problem, traversing the tree level by level. It uses a queue to manage nodes to visit.

Time: O(n)Space: O(w)

Trade-offs: BFS might use more space than DFS in a skewed tree because the queue can store all the nodes at the widest level of the tree (w). In a balanced tree, the space complexity is similar to DFS.

✨

Key Insights

1**Leaf-Node Specific Sum Check:** The `targetSum` comparison is strictly performed *only* when a `node` is confirmed to be a leaf (`not node.left and not node.right`). This precisely adheres to the 'root-to-leaf' requirement and distinguishes it from problems asking for path sums ending at any arbitrary node.
2**Cumulative Sum through Recursion State:** The `current_sum` isn't a global variable. Instead, it's passed as an argument in each recursive call. This elegant pattern ensures that each branch of the DFS independently maintains its path's sum, naturally 'undoing' parent sums as the call stack unwinds and preventing interference between sibling paths.
3**Early Exit with Logical `or`:** The `dfs(node.left, current_sum) or dfs(node.right, current_sum)` structure provides an efficient short-circuiting mechanism. As soon as *any* left or right branch finds a valid path summing to `targetSum`, the `or` condition evaluates to `true`, and subsequent explorations (e.g., of the right subtree if the left finds a path) are completely bypassed, optimizing execution time.

📚

Key Terms Explained

For Students

Tree

Hierarchical structure with nodes. Like a family tree!

Edge Cases

Edge case 1: Empty tree (root is null). The solution correctly handles this by returning `false` immediately.
Edge case 2: A tree with only one node. The solution correctly checks if the single node's value equals the targetSum.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Incorrectly handling the base case. Failing to account for the case where a leaf node is reached and its value needs to be checked against the targetSum.

✗Common mistake 2: Forgetting to subtract the current node's value from the `targetSum` in the recursive calls. This would lead to incorrect sum calculations.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Evaluating network paths. A tree-like structure could represent a network, and this algorithm could determine if a path exists with a certain total weight (e.g., cost, latency).

🏦Real-world scenario 2: Analyzing decision trees. In machine learning, decision trees represent decisions and their consequences. This algorithm could be used to find a decision path that leads to a desired outcome.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

Most tree problems can be solved recursively. The base case is usually a null node. Think about what information needs to flow up vs down the tree.

🎯 Interview Tip

Use this problem to demonstrate clean code practices. Variable naming and code organization matter.

⚠️ Watch Out

Not handling null nodes properly. Always check if the current node exists before accessing its children.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: September 21, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 13

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 6

❓

Frequently Asked Questions

How do I choose between recursive and iterative tree traversal?

Use recursive traversal for cleaner code when stack depth isn't a concern (tree height < ~1000). Use iterative with explicit stack for very deep trees to avoid stack overflow. Iterative is also preferred when you need fine-grained control over the traversal process.

How should I approach easy-level algorithm problems?

Easy problems build foundational skills. Focus on: 1) Understanding the problem completely before coding, 2) Writing clean, readable code, 3) Handling all edge cases (empty input, single element, etc.), 4) Analyzing time and space complexity. Don't skip complexity analysis even for simple solutions.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Path Sum"?

For this easy-level Tree problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether depth-first search techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?