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

You're given a binary tree and a target value K. List every downward path (following parent-to-child links, starting from any node) whose values add up to K.

Input Format
Implement kSumPaths(root, k). Inputs below show JavaScript function arguments; there is no stdin parsing. Trees use level-order arrays with null for missing children. The editor passes nodes with val, left, and right properties; [] becomes null.
Output Format
Return the result described in the statement. The order of the outer result array does not matter.

Sample Input and Output

Example 1 · Run Sample

Input
root = [1,2,3]
k = 3
Output
[[1,2],[3]]

Example 2

Input
root = [1]
k = 2
Output
[]
Constraints
  • 1 <= N <= 10^4
  • -10^4 <= Node.val <= 10^4
Test Cases (2)
Case 1
Args: [[1,2,3],3] Expected: [[1,2],[3]]
Case 2
Args: [[1],2] Expected: []
Topics
TreeBinary TreeDFS

DFS with Path Tracking

javascript
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 × h + P), where h is height and P is the total length of returned paths | Space: O(h) auxiliary space, excluding output

Saved in this browser only. Private to you.

JavaScript