DSA 450 Notes

Problem Statement

Given a binary tree and a number k, print all paths (from any node to any descendant) that sum to k. A path can start from any node and end at any node in the downward direction.

Example:

        1
       / \
      3   -1
     / \   \
    2   1   4
       /   / \
      1   1   2
             \
              6

k = 5

Paths with sum 5:
- 3 → 2
- 3 → 1 → 1
- 1 → 3 → 1
- -1 → 4 → 2
- 1 → 4

Output: Print all these paths

Approach 1: Brute Force (Check All Paths from Each Node)

Intuition

For each node, check all paths starting from that node going downward. If any path sums to k, print it. This requires exploring all possible paths from each node.

Algorithm

For each node in the tree, start a path search
From each starting node, explore all downward paths
Track current path and sum
When sum equals k, print the path
Continue exploring (don't stop, as negative values may exist)

java

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    private void printPath(List<Integer> path) {
        for (int i = 0; i < path.size(); i++) {
            System.out.print(path.get(i));
            if (i < path.size() - 1) System.out.print(" -> ");
        }
        System.out.println();
    }
    
    // Find all k-sum paths starting from this node going downward
    private void findPathsFromNode(TreeNode root, int k, List<Integer> path, 
                                    int sum, List<List<Integer>> result) {
        if (root == null) return;
        
        path.add(root.val);
        sum += root.val;
        
        // Check if current path sums to k
        if (sum == k) {
            result.add(new ArrayList<>(path));
        }
        
        // Continue searching
        findPathsFromNode(root.left, k, path, sum, result);
        findPathsFromNode(root.right, k, path, sum, result);
        
        // Backtrack
        path.remove(path.size() - 1);
    }
    
    // Visit each node and find paths starting from it
    public List<List<Integer>> printKSumPaths(TreeNode root, int k) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        
        List<Integer> path = new ArrayList<>();
        findPathsFromNode(root, k, path, 0, result);
        
        // Also check paths starting from children
        result.addAll(printKSumPaths(root.left, k));
        result.addAll(printKSumPaths(root.right, k));
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n^2) - For each node, we may traverse all nodes below it
Space Complexity: O(n^2) - Storing all paths, each can be O(n) length

Approach 2: Optimal (Single Traversal with Path Array)

Intuition

Maintain the path from root to current node. At each node, check all suffixes of this path for sum k. This avoids starting a new traversal from each node.

Algorithm

Maintain path array from root to current node
At each node, check all suffixes of path ending at current node
If any suffix sums to k, print it
Recursively process children
Backtrack when returning

java

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    private void findKSumPaths(TreeNode root, int k, List<Integer> path,
                               List<List<Integer>> result) {
        if (root == null) return;
        
        // Add current node to path
        path.add(root.val);
        
        // Check all suffixes of path ending at current node
        int sum = 0;
        for (int i = path.size() - 1; i >= 0; i--) {
            sum += path.get(i);
            if (sum == k) {
                result.add(new ArrayList<>(path.subList(i, path.size())));
            }
        }
        
        // Recurse for children
        findKSumPaths(root.left, k, path, result);
        findKSumPaths(root.right, k, path, result);
        
        // Backtrack
        path.remove(path.size() - 1);
    }
    
    public List<List<Integer>> printKSumPaths(TreeNode root, int k) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        findKSumPaths(root, k, path, result);
        return result;
    }
}

Using Prefix Sum HashMap (Most Optimal)

Complexity Analysis

Time Complexity: O(n) - Each node is visited once, suffix check is O(h) per node
Space Complexity: O(h) - Path array stores at most h elements (tree height)

Key Takeaways

Path suffix checking: At each node, check all suffixes ending at that node
Prefix sum technique: Using hashmap to find subarrays with given sum
Backtracking essential: Must remove current node from path when returning
Don't stop early: Even after finding sum = k, continue (negative values may exist)
Similar to: Subarray sum equals k problem, but on tree structure

Print all K Sum paths in a Binary tree

Problem Statement

Approach 1: Brute Force (Check All Paths from Each Node)

Intuition

Algorithm

Complexity Analysis

Approach 2: Optimal (Single Traversal with Path Array)

Intuition

Algorithm

Using Prefix Sum HashMap (Most Optimal)

Complexity Analysis

Key Takeaways