Path Sum III

 

Problem Statement: Given a binary tree and a sum, find the number of paths in the tree that sum up to the given sum. The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

1. Clarify the problem:

  • Can the values of nodes be negative or zero?
  • Can the given sum be negative or zero?
  • Are we guaranteed that the tree is non-empty?

2. Analyze the problem:

  • Input: Binary tree, integer sum
  • Output: Integer representing the number of paths in the tree that sum up to the given sum
  • Constraints:
    • The values of nodes can be any integer.
    • The given sum can be any integer.
    • The tree can be empty.

3. Design an algorithm:

  • We can solve this problem using a recursive approach combined with depth-first search (DFS).
  • For each node in the tree, we will recursively explore all possible paths starting from that node.
  • At each node, we will calculate the sum of the current path from the root to the current node.
  • If the current path sum equals the given sum, we will increment a counter variable to keep track of the number of paths found.
  • We will continue exploring all possible paths by recursively calling the function on the left and right child nodes.
  • Finally, we will return the total number of paths found.

4. Explain your approach:

  • We will use a recursive approach with depth-first search to explore all possible paths in the tree.
  • At each node, we calculate the sum of the current path from the root to the current node.
  • If the current path sum equals the given sum, we increment a counter variable to keep track of the number of paths found.
  • We continue exploring all possible paths by recursively calling the function on the left and right child nodes.
  • The base case for the recursion is when we reach a None node (leaf node or empty tree).

5. Write clean and readable code:

python
class Solution:
    def pathSum(self, root, sum):
        self.count = 0
        self.dfs(root, sum)
        return self.count

    def dfs(self, node, target):
        if node is None:
            return

        self.checkPath(node, target)
        self.dfs(node.left, target)
        self.dfs(node.right, target)

    def checkPath(self, node, target):
        if node is None:
            return

        if node.val == target:
            self.count += 1

        self.checkPath(node.left, target - node.val)
        self.checkPath(node.right, target - node.val)

6. Test your code: I will test the code with the following test cases:

  • Test case 1: Tree with paths that sum up to the given sum.
  • Test case 2: Tree with no paths that sum up to the given sum.
  • Test case 3: Empty tree.
python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# Test case 1
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(-3)
root.left.left = TreeNode(3)
root.left.right = TreeNode(2)
root.left.left.left = TreeNode(3)
root.left.left.right = TreeNode(-2)
root.left.right.right = TreeNode(1)
root.right.right = TreeNode(11)
solution = Solution()
print(solution.pathSum(root, 8))  # Expected output: 3

# Test case 2
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left.left = TreeNode(11)
root.right.left = TreeNode(13)
root.right.right = TreeNode(4)
root.left.left.left = TreeNode(7)
root.left.left.right = TreeNode(2)
root.right.right.left = TreeNode(5)
root.right.right.right = TreeNode(1)
print(solution.pathSum(root, 22))  # Expected output: 3

# Test case 3
root = None
print(solution.pathSum(root, 1))  # Expected output: 0

7. Optimize if necessary: The given algorithm has a time complexity of O(N^2) in the worst case, where N is the number of nodes in the tree. This is because, in the worst case, each node can be the starting point for a path, and for each starting point, we traverse all its descendant nodes.

We can optimize the algorithm by using a prefix sum technique. Instead of recalculating the path sum from the root to each node in every recursive call, we can keep track of the prefix sum at each node and check if there exists a path from any ancestor node to the current node with a sum equal to the given sum. This way, we avoid redundant calculations.

The optimized code would look as follows:

python
class Solution:
    def pathSum(self, root, sum):
        self.count = 0
        prefix_sums = {0: 1}  # Prefix sums and their counts
        self.dfs(root, sum, 0, prefix_sums)
        return self.count

    def dfs(self, node, target, curr_sum, prefix_sums):
        if node is None:
            return

        curr_sum += node.val
        complement = curr_sum - target
        self.count += prefix_sums.get(complement, 0)

        prefix_sums[curr_sum] = prefix_sums.get(curr_sum, 0) + 1
        self.dfs(node.left, target, curr_sum, prefix_sums)
        self.dfs(node.right, target, curr_sum, prefix_sums)
        prefix_sums[curr_sum] -= 1  # Remove the current sum from the prefix sums

The optimized algorithm has a time complexity of O(N) and a space complexity of O(N), where N is the number of nodes in the tree.

Next Post Previous Post