# Find ALL the paths in a binary tree equal to a sum

• This question was asked for an SDE 2 position.

For example, given the following binary tree:

[2,3,5,4,8,6,-2,null,null,null,null,null,null,null,2] and sum = 7

``````                            2
/     \
3         5
/     \    /   \
4       8  6     -2
\
2
``````

Print : [3,4] , [2,5] , [2,5,-2,2]

• From each node in the tree, find the paths that add up to the sum. As a node is traversed, decrease the sum being targeted. For a balanced tree, this runs in O(n log n).

``````#include <vector>

// O(n log n) for a balanced tree.
std::size_t gNodesVisited = 0;

struct Node
{
int value;
Node* left;
Node* right;

Node()
: value(0), left(nullptr), right(nullptr)
{
}
};

// Find the paths that add up to the sum.  root's value must be taken.
void findPathsWithSum2(Node* const root, const int sum,
std::vector<int>& currPath, std::vector<std::vector<int>>& paths)
{
++gNodesVisited;

currPath.push_back(root->value);
const int remainder = sum - root->value;
if (0 == remainder)
{
paths.push_back(currPath);
}

if (root->left)
{
findPathsWithSum2(root->left, remainder, currPath, paths);
}
if (root->right)
{
findPathsWithSum2(root->right, remainder, currPath, paths);
}
currPath.pop_back();
}

// Find the paths that add up to the sum by trying every node in the tree as a
// starting point.
void findPathsWithSum(Node* const root, const int sum,
std::vector<std::vector<int>>& paths)
{
if (nullptr == root)
{
return;
}

std::vector<int> currPath;
findPathsWithSum2(root, sum, currPath, paths);

findPathsWithSum(root->left, sum, paths);
findPathsWithSum(root->right, sum, paths);
}

void main()
{
const int null = INT_MIN;
const int binaryTree[]
= { 2, 3, 5, 4, 8, 6, -2, null, null, null, null, null, null, null, 2 };
const std::size_t size = sizeof(binaryTree) / sizeof(int);
const int sum = 7;

if (0 < size)
{
Node* const nodes = new Node[size];
for (auto i = 0; i < size; ++i)
{
nodes[i].value = binaryTree[i];
const std::size_t leftIndex = 2 * i + 1;
if (leftIndex < size)
{
if (null != binaryTree[leftIndex])
{
nodes[i].left = &nodes[leftIndex];
}
}
const std::size_t rightIndex = 2 * i + 2;
if (rightIndex < size)
{
if (null != binaryTree[rightIndex])
{
nodes[i].right = &nodes[rightIndex];
}
}
}

std::vector<std::vector<int>> paths;
findPathsWithSum(&nodes[0], sum, paths);
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.