We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Path Sum II

Number: 113

Difficulty: Medium

Paid? No

Companies: Meta, Amazon, Microsoft, Google, Oracle, TikTok, Walmart Labs, Bloomberg

Problem Description

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values equals targetSum. A leaf is a node with no children, and each path should be returned as a list of node values (not node references).

Key Insights

  • Use Depth-First Search (DFS) to explore all paths from the root to the leaves.
  • Backtracking is essential: add the current node value to the path before the recursive calls and remove it (backtrack) after exploring both subtrees.
  • At each leaf, check if the accumulated sum equals targetSum.
  • Maintain a running sum or subtract the current node's value from the target sum as you traverse.

Space and Time Complexity

Time Complexity: O(N^2) in the worst-case scenario (where N is the number of nodes) when most nodes are leaf nodes, since each potential path copy operation can be O(N). Space Complexity: O(N) for the recursion stack and the path storage, where N is the height of the tree.

Solution

We solve the problem using a recursive DFS approach combined with backtracking. The idea is to traverse the tree while maintaining the current path and the remaining sum needed to reach targetSum. When a leaf node is reached (node with no children), we check if the remaining sum equals the leaf's value – if yes, we record a copy of the current path.

Data structures and algorithmic approaches used:

  • Recursion for DFS: to traverse to each leaf.
  • List (or Array) for storing the current path.
  • Backtracking: to remove the last added element when stepping back up the recursion stack.
  • Copying the path when a valid leaf is reached to store it in the final result.

A common pitfall is to forget to backtrack, which would result in incorrect paths being recorded.

Code Solutions

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

def pathSum(root, targetSum):
    result = []  # This will store all valid paths

    def dfs(node, current_path, remaining_sum):
        if not node:
            return  # Base case: reached the end of a path

        # Add the current node's value to the path
        current_path.append(node.val)

        # Check if it's a leaf and if the path sum equals targetSum
        if not node.left and not node.right and node.val == remaining_sum:
            result.append(list(current_path))  # Add a copy of the current path
        else:
            # Continue the search in the left and right subtrees
            dfs(node.left, current_path, remaining_sum - node.val)
            dfs(node.right, current_path, remaining_sum - node.val)

        # Backtrack: remove the last element before returning to the caller
        current_path.pop()

    dfs(root, [], targetSum)
    return result
← Back to All Questions