What is the time complexity of Path Sum II?

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

What data structures are used to solve Path Sum II?

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

What are the key insights for solving Path Sum II?

Insight 1: The core idea is to use Depth-First Search (DFS) to explore all possible paths from the root to the leaves. Insight 2: Backtracking is crucial to explore different branches of the tree. After exploring a path, we need to 'backtrack' (undo the choices) to explore other paths.

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

Path Sum II - LeetCode 113 Solution

Q: Which companies ask LeetCode 113. Path Sum II in interviews?

This problem is frequently asked at Arista Networks, DoorDash, Flipkart, Oracle, TikTok and 1 more companies.

Path Sum II - Complete Solution Guide

Path Sum II is LeetCode problem 113, a Medium 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 all root-to-leaf paths where the sum of the node values in the path equals targetSum . Each path should be returned as a list of the node values , not node references . A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children. Example 1: Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 Output: [[5,4,11,2],[5,8,4,5]] Explanation: There are two paths whos

Detailed Explanation

The problem asks us to find all paths from the root node to leaf nodes in a binary tree such that the sum of the node values along each path equals a given target sum. The output should be a list of lists, where each inner list represents a path with node values adding up to the target sum. A 'leaf' node is defined as a node with no children (neither left nor right child). We need to return the paths as lists of integers representing node *values*, not node references.

Solution Approach

The provided solutions use a recursive Depth-First Search (DFS) approach with backtracking. We start at the root node and recursively explore the left and right subtrees. At each node, we add its value to the current path and subtract it from the remaining sum. When we reach a leaf node, we check if the remaining sum is zero. If it is, we add the current path to the results. After exploring a subtree, we remove the current node's value from the current path (backtracking) so that we can explore other possible paths. This ensures we consider every possible root-to-leaf path.

Step-by-Step Algorithm

Step 1: Initialize an empty list `results` to store the paths that sum up to the `targetSum`.
Step 2: Define a recursive function `dfs(node, current_path, remaining_sum)` to perform Depth-First Search.
Step 3: Base Case: If the current node is `null`, return immediately because there's no path to explore.
Step 4: Add the current node's value to the `current_path` and subtract it from the `remaining_sum`.
Step 5: Check if the current node is a leaf node (no left and right children).
Step 6: If it's a leaf node and `remaining_sum` is 0, then we found a valid path. Create a copy of the `current_path` and add it to the `results`.
Step 7: If the current node is not a leaf node, recursively call `dfs` on the left and right children, passing the updated `current_path` and `remaining_sum`.
Step 8: Backtrack: After exploring the left and right subtrees, remove the last element from the `current_path`. This step is crucial to explore different branches of the tree.
Step 9: Call the `dfs` function with the `root`, an empty `current_path`, and the `targetSum`.
Step 10: Return the `results` list containing all the paths that sum up to the `targetSum`.

Key Insights

Insight 1: The core idea is to use Depth-First Search (DFS) to explore all possible paths from the root to the leaves.
Insight 2: Backtracking is crucial to explore different branches of the tree. After exploring a path, we need to 'backtrack' (undo the choices) to explore other paths.
Insight 3: We need to keep track of the current path and the remaining sum. When we reach a leaf node, we check if the remaining sum is zero. If it is, we have found a valid path.

Complexity Analysis

Time Complexity: O(N)

Space Complexity: O(N)

Topics

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

Companies

Asked at: Arista Networks, DoorDash, Flipkart, Oracle, TikTok, Walmart Labs.

Path Sum II | LeetCode 113

Medium

Backtracking Tree Depth-First Search Binary Tree

Time: O(N)Space: O(N)

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 List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> results = new ArrayList<>();

        dfs(root, new ArrayList<>(), targetSum, results);
        return results;
    }

    private void dfs(TreeNode node, List<Integer> currentPath, int remainingSum, List<List<Integer>> results) {
        if (node == null) {
            return;
        }

        currentPath.add(node.val);
        remainingSum -= node.val;

        // If it's a leaf node, check if the path sum is equal to targetSum
        if (node.left == null && node.right == null) {
            if (remainingSum == 0) {
                results.add(new ArrayList<>(currentPath));
            }
        } else {
            // Continue to search in left and right children
            dfs(node.left, currentPath, remainingSum, results);
            dfs(node.right, currentPath, remainingSum, results);
        }

        // Backtrack: remove the current node from the path to explore other branches
        currentPath.remove(currentPath.size() - 1);
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 113: Path Sum II - Detailed explanation and solution approaches.

Topics

Backtracking Tree Depth-First Search Binary Tree

Companies

Arista NetworksDoorDashFlipkartOracleTikTokWalmart Labs

Stats

Difficulty:Medium

Languages:4

Companies:6

Problem #:113

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

10 steps

1
Step 1: Initialize an empty list `results` to store the paths that sum up to the `targetSum`.
2
Step 2: Define a recursive function `dfs(node, current_path, remaining_sum)` to perform Depth-First Search.
3
Step 3: Base Case: If the current node is `null`, return immediately because there's no path to explore.
4
Step 4: Add the current node's value to the `current_path` and subtract it from the `remaining_sum`.
5
Step 5: Check if the current node is a leaf node (no left and right children).
6
Step 6: If it's a leaf node and `remaining_sum` is 0, then we found a valid path. Create a copy of the `current_path` and add it to the `results`.
7
Step 7: If the current node is not a leaf node, recursively call `dfs` on the left and right children, passing the updated `current_path` and `remaining_sum`.
8
Step 8: Backtrack: After exploring the left and right subtrees, remove the last element from the `current_path`. This step is crucial to explore different branches of the tree.
9
Step 9: Call the `dfs` function with the `root`, an empty `current_path`, and the `targetSum`.
10
Step 10: Return the `results` list containing all the paths that sum up to the `targetSum`.

💡

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)

💾

Space Complexity

O(N)

📝

Why?

The time complexity is O(N) because in the worst case we visit each node once. The space complexity is O(N) because the recursion stack can grow to the height of the tree (which can be N in a skewed tree), and the current path can also have at most N elements, in addition to output list of size O(N) in the worst case where every path sums to target.

📖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 Approach with Stack

An iterative approach using a stack to simulate the DFS traversal can also be implemented. This avoids recursion and potentially improves performance for extremely deep trees.

Time: O(N)Space: O(N)

Trade-offs: While it avoids recursion overhead, the iterative approach is generally more complex to implement and understand than the recursive approach. The space complexity remains O(N) due to the stack used to store nodes and the current path.

✨

Key Insights

1Insight 1: The core idea is to use Depth-First Search (DFS) to explore all possible paths from the root to the leaves.
2Insight 2: Backtracking is crucial to explore different branches of the tree. After exploring a path, we need to 'backtrack' (undo the choices) to explore other paths.
3Insight 3: We need to keep track of the current path and the remaining sum. When we reach a leaf node, we check if the remaining sum is zero. If it is, we have found a valid path.

📚

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 an empty list of paths since the `dfs` function returns immediately if it receives a null node.
Edge case 2: No paths sum to the target sum. The solution correctly handles this case by returning an empty list, as no paths will be added to the `results` list.
Edge case 3: The target sum is 0 and the tree contains negative values. The algorithm accurately identifies paths that sum to zero, even with negative node values.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not creating a *copy* of the `current_path` when adding it to the `results`. Modifying the original `current_path` after adding it will corrupt the results because it is a reference to the same list.

✗Common mistake 2: Forgetting to backtrack by removing the current node from the `current_path` after exploring its children. This will lead to incorrect paths being generated.

✗Common mistake 3: Not handling the base case of a null node correctly, which can lead to a null pointer exception.

✅

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: Pathfinding algorithms in games or robotics. This problem is a simplified version of finding paths that satisfy certain conditions in a graph. For example, finding paths with certain cost constraints.

🏦Real-world scenario 2: Network routing. Determining if a path exists within a network topology that satisfies specific bandwidth or latency requirements can be solved with similar backtracking techniques.

🎮Real-world scenario 3: Decision Tree analysis. Finding paths through a decision tree that lead to a particular outcome can be viewed as an analogous problem.

💡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

Backtracking = DFS + pruning. The key is identifying when to backtrack. Always restore state after recursion.

🎯 Interview Tip

Consider multiple approaches before coding. Mentioning alternatives shows breadth of knowledge.

⚠️ Watch Out

Always test your solution with edge cases: empty input, single element, and boundary values.

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

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

@CodeNinjaJul 13

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 6

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jun 29

❓

Frequently Asked Questions

How do I avoid duplicate solutions in backtracking?

Sort the input first, then skip consecutive duplicates at the same recursion level: if (i > start && nums[i] == nums[i-1]) continue. For permutations, use a visited array or swap-based approach. Always consider if order matters (permutations vs combinations).

What is the difference between DFS and BFS for trees?

DFS (using recursion or stack) explores depth-first, useful for path-finding and backtracking problems. BFS (using queue) explores level-by-level, ideal for finding shortest paths or processing nodes by depth. Choose based on whether level information matters.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Path Sum II"?

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

🤖 Need help with this problem?