Algorithm to print all paths with a given sum in a binary tree

Question

The following is an interview question.

You are given a binary tree (not necessarily BST) in which each node contains a value. Design an algorithm to print all paths which sum up to that value. Note that it can be any path in the tree - it does not have to start at the root.

Although I am able to find all paths in tree that start at the root have the given sum, I am not able to do so for paths not not starting at the root.

Answer 1

Well, this is a tree, not a graph. So, you can do something like this:

Pseudocode:

global ResultList

function ProcessNode(CurrentNode, CurrentSum)
    CurrentSum+=CurrentNode->Value
    if (CurrentSum==SumYouAreLookingFor) AddNodeTo ResultList
    for all Children of CurrentNode
          ProcessNode(Child,CurrentSum)

Well, this gives you the paths that start at the root. However, you can just make a tiny change:

    for all Children of CurrentNode
          ProcessNode(Child,CurrentSum)
          ProcessNode(Child,0)

You might need to think about it for a second (I'm busy with other things), but this should basically run the same algorithm rooted at every node in the tree

EDIT: this actually gives the "end node" only. However, as this is a tree, you can just start at those end nodes and walk back up until you get the required sum.

EDIT 2: and, of course, if all values are positive then you can abort the descent if your current sum is >= the required one