Print all k-sum paths in a binary tree Hard 0 attempts
GeeksforGeeks ↗

Print all k-sum paths in a binary tree

Hard TreeBinary TreeDFS GeeksforGeeks

Given a binary tree and a target sum K, print all paths from any node that sum to K.

Example: tree with various paths summing to K

Sample Input
—
Sample Output
—
Constraints
  • 1 <= N <= 10^4
  • -10^4 <= Node.val <= 10^4
Topics
TreeBinary TreeDFS

DFS with Path Tracking

function kSumPaths(root, k) {
  const result = [];
  function dfs(node, path) {
    if (!node) return;
    path.push(node.val);
    let sum = 0;
    for (let i = path.length-1; i >= 0; i--) {
      sum += path[i];
      if (sum === k) result.push(path.slice(i));
    }
    dfs(node.left, path); dfs(node.right, path);
    path.pop();
  }
  dfs(root, []);
  return result;
}

Time: O(n²) | Space: O(n)

Saved in this browser only. Private to you.

JavaScript