algoadvance

Leetcode 437. Path Sum III

Problem Statement

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the tree’s node values are in the range -1,000,000 to 1,000,000.

Clarifying Questions

  1. Can the path contain only one node?
    • Yes, the path can contain a single node.
  2. Will the path sum always be a positive integer?
    • No, the target sum can be negative or zero as well.
  3. Should the solution work for trees that are not balanced (i.e., skewed trees)?
    • Yes, the solution should handle any valid binary tree structure.
  4. Do the node values need to be distinct?
    • No, node values can be repeated.

Strategy

To solve this problem, we need to consider every possible path that starts from any node and calculate the path sum recursively.

We can break down the solution into two main parts:

  1. A function to find if there’s a path starting from the current node with a sum that equals the target sum.
  2. A function that recursively traverses the whole tree and checks for paths starting from each node.

We can achieve this through Depth-First Search (DFS).

// TreeNode definition as per usual for binary trees.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class PathSumIII {
    public int pathSum(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        
        // Count paths with sum starting from the root
        int pathsFromRoot = countPathsFromNode(root, sum);
        
        // Try the left and right subtrees
        int pathsFromLeftSubtree = pathSum(root.left, sum);
        int pathsFromRightSubtree = pathSum(root.right, sum);
        
        // Total paths are paths starting from the root, plus the left and right subtree paths
        return pathsFromRoot + pathsFromLeftSubtree + pathsFromRightSubtree;
    }
    
    private int countPathsFromNode(TreeNode node, int sum) {
        if (node == null) {
            return 0;
        }
        
        // Do we have a path ending at this node?
        int count = (node.val == sum) ? 1 : 0;
        
        // Continue the path to the left and right child
        count += countPathsFromNode(node.left, sum - node.val);
        count += countPathsFromNode(node.right, sum - node.val);
        
        return count;
    }
}

Time Complexity

Thus, the overall time complexity is O(n^2) in the worst case. While this is not optimal for very large trees, it is feasible given the constraint of the problem where n can be at most 1,000 nodes.

Additional Notes

For very large inputs or to further optimize, you can use a prefix sum approach with a HashMap to store cumulative frequencies. This will bring down the time complexity to O(n). However, the above approach is simpler to understand and implement for typical binary tree problems.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI