## Print all k-sum paths in a binary tree

## Introduction

Binary Trees are the indispensable data structures of the interviews. Mostly because they are hard to understand and can change the complexity drastically; usually from O(n) to O(log(n)). Trees are the representatives of divide and conquer approach in the data structures, open to mind confusing recursive algorithms.

## Problem

A binary tree with integer data and a number k are given. Print every path in the tree with sum of the nodes in the path as k.

A path can start from any node and end at any node, i.e. they need not be root node and leaf node; and negative numbers can also be there in the tree.

here is where I first saw the problem : http://www.geeksforgeeks.org/amazon-interview-experience-set-323-software-development-engineer-off-campus/

but couldn’t understand it and found http://www.geeksforgeeks.org/print-k-sum-paths-binary-tree/ where I copied the problem definition from.

## Solution

My approach is basic, first think about a Tree with root only, if its value is equal to the given value then it is a solution. Now lets add a left and a right node. In this case as we go deeper on the tree we need to look for;

- starting from root, is the sum equals to the given value
- starting from the left is the sum equals to the given value and same for right

Hard part is collecting the correct path information.

The BST in solution hold lower values on the left and BST may contain negative values.

Here is the code;

void findSum(Integer originalSum, Integer sum, List<List<Integer>> result, List<Integer> currentList, Node node) { if (node == null) return; Integer nodeValue = node.value; currentList.add(nodeValue); if (Objects.equals(sum, nodeValue)) { List<Integer> resultL = new ArrayList(currentList); result.add(resultL); } // as the BST may contain negative values we have to iterate it all findSum(originalSum, originalSum, result, new ArrayList(), node.right); findSum(originalSum, originalSum, result, new ArrayList(), node.left); int remaining = sum - nodeValue; findSum(originalSum, remaining, result, new ArrayList(currentList), node.left); findSum(originalSum, remaining, result, new ArrayList(currentList), node.right); } public void findSum(Integer sum) { List<List<Integer>> result = new ArrayList<>(); findSum(sum, sum, result, new ArrayList<>(), root); System.out.println(result); }

## Conclusion

The complexity of my solution is O(n^2) hope it is not a concern for you 🙂

I know my solution is terrible with brute-force but having negative values is the problem here, besides that the long signature is also terrifying but we have to carry the original value to start testing from any node.

By the way solution on http://www.geeksforgeeks.org/print-k-sum-paths-binary-tree/ is not working or I couldn’t make it work for some reason.