DKodeTree Small Logo
DKodeTreeWhere logic takes root...!
Path Sum III - Solution
Solutions and explanations
Link to Problem StatementView on GitHub

# 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
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        if not root:
            return 0

        def count_paths_from(node, target):
            if not node:
                return 0
            paths_from_left_child = count_paths_from(node.left, target - node.val)
            paths_from_right_child = count_paths_from(node.right,  target - node.val)
            return (node.val == target) + paths_from_left_child + paths_from_right_child

        return count_paths_from(root, targetSum) + self.pathSum(root.left,targetSum) + self.pathSum(root.right, targetSum)

Complexity Analysis

Here, n is the number of nodes, and h is the height of the binary tree.

  • Time Complexity: O(n²)

    • For each node, we start a DFS to find all paths starting from that node.
    • Each path DFS may traverse up to h nodes, and in a skewed tree, h = n.
      • In the best case (a balanced tree), h = log n.
      • In the worst case (a skewed tree), h = n, so the recursion stack uses O(n) space.
    • So in the worst case, every node can trigger a full DFS, resulting in O(n²).

  • Space Complexity: O(h)

    • Recursion Stack: O(h) — one stack frame per level of DFS.

# 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
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        prefix_sum_cnt = collections.defaultdict(int)
        prefix_sum_cnt[0] = 1   # Base case: empty path sum

        def dfs(node, cur_sum):
            if not node:
                return 0

            cur_sum += node.val
            count = prefix_sum_cnt[cur_sum - targetSum]  # Paths ending here where prev_sum = cur_sum - targetSum

            prefix_sum_cnt[cur_sum] += 1    # Add current prefix sum to the map
            count += dfs(node.left, cur_sum) + dfs(node.right, cur_sum)
            prefix_sum_cnt[cur_sum] -= 1    # Remove current prefix sum before returning
            return count

        return dfs(root, 0)

Complexity Analysis

Here, n is the number of nodes, and h is the height of the binary tree.

  • Time Complexity: O(n)

    • Each node is visited once during DFS.
    • And at each node, the operations on the prefix sum hashmap (insert, lookup, delete) take O(1) time. So, for n nodes the time taken is O(n).

  • Space Complexity: O(n)

    • Recursion Stack: O(h) — one stack frame per level of the tree.
    • Prefix sum hashmap: O(h) — stores at most one entry per node along the current path.

    In the best case (a balanced tree), h = log n, so space ≈ O(log n).
    In the worst case (a skewed tree), h = n, so space ≈ O(n).