This is original an Amazon interview question for software developer engineer from careercup. Here is the thread,
"
2. Analysis
This is a typical tree search problem. Both BFS and DFS can be used. Assuming that everyone is clear, BFS and DFS are nearly using the same code except that BFS uses queue to take the children nodes and DFS uses stacks to take the children node. It is easy to distinguish this because BFS will traverse the children at lower level to the deep level but DFS will traverse from the deepest level upwards.
For this particular problem the only change we need to do comparing with normal tree traversal is to take the sum value towards its direct parent together with its node pointer into the queue or stack for BFS and DFS respectively.
3. C++ Implementation
Find the number of path only
- Assume that all the values are all positive
// ********************************************************************************
#include <queue>
#include <stack>
struct TreeNode
{
int value;
TreeNode* left;
TreeNode* right;
};
struct NodeSumPair
{
TreeNode* node;
size_t sum; // sum from root to its parent node
NodeSumPair(TreeNode* curNode, size_t curSum)
: node(curNode)
, sum(curSum)
{}
};
size_t FindNumOfPathsDFS(TreeNode* root, size_t sum)
{
std::stack<NodeSumPair> curStack;
size_t curSum = 0;
curStack.push(NodeSumPair(root, curSum));
size_t result = 0;
while (!curStack.empty()) {
const NodeSumPair& curPair = curStack.top();
if (curPair.node) {
curSum = curPair.sum + curPair.node->value;
if (curSum == sum) {
++result; // continue because of all positive numbers
continue;
}
else if (curSum > sum) {
continue;
}
curStack.push(NodeSumPair(curPair.node->right, curSum));
curStack.push(NodeSumPair(curPair.node->left, curSum));
}
curStack.pop();
}
return result;
}
size_t FindNumOfPathsBFS(TreeNode* root, size_t sum)
{
std::queue<NodeSumPair> curQueue;
size_t curSum = 0;
curQueue.push(NodeSumPair(root, curSum));
size_t result = 0;
while (!curQueue.empty()) {
NodeSumPair curPair = curQueue.front();
if (curPair.node) {
curSum = curPair.sum + curPair.node->value;
if (curSum == sum) {
++result; // continue because of all positive numbers
continue;
}
else if (curSum > sum) {
continue;
}
curQueue.push(NodeSumPair(curPair.node->left, curSum));
curQueue.push(NodeSumPair(curPair.node->right, curSum));
}
curQueue.pop();
}
return result;
}
// ********************************************************************************
Return the path as well
- Assume all positive number
- Change the tree structure to take parent node in the tree node
// ********************************************************************************
#include <queue>
#include <stack>
struct TreeNode
{
int value;
TreeNode* parent; // go upwards to find the path
TreeNode* left;
TreeNode* right;
};
struct NodeSumPair
{
TreeNode* node;
size_t sum;
NodeSumPair(TreeNode* curNode, size_t curSum)
: node(curNode)
, sum(curSum)
{}
};
std::vector<TreeNode*> FindNumOfPathsDFS(TreeNode* root, size_t sum)
{
std::stack<NodeSumPair> curStack;
size_t curSum = 0;
curStack.push(NodeSumPair(root, curSum));
std::vector<TreeNode*> result;
while (!curStack.empty()) {
const NodeSumPair& curPair = curStack.top();
if (curPair.node) {
curSum = curPair.sum + curPair.node->value;
if (curSum == sum) {
result.push_back(curPair.node); // node found
continue;
}
else if (curSum > sum) {
continue;
}
curStack.push(NodeSumPair(curPair.node->right, curSum));
curStack.push(NodeSumPair(curPair.node->left, curSum));
}
curStack.pop();
}
return result;
}
std::vector<TreeNode*> FindNumOfPathsBFS(TreeNode* root, size_t sum)
{
std::queue<NodeSumPair> curQueue;
size_t curSum = 0;
curQueue.push(NodeSumPair(root, curSum));
std::vector<TreeNode*> result;
while (!curQueue.empty()) {
NodeSumPair curPair = curQueue.front();
if (curPair.node) {
curSum = curPair.sum + curPair.node->value;
if (curSum == sum) {
result.push_back(curPair.node); // node found
continue;
}
else if (curSum > sum) {
continue;
}
curQueue.push(NodeSumPair(curPair.node->left, curSum));
curQueue.push(NodeSumPair(curPair.node->right, curSum));
}
curQueue.pop();
}
return result;
}
// ********************************************************************************
Return the path and no assumption
- The value can be any negative, 0 or positive
// ********************************************************************************
#include <queue>
#include <stack>
struct TreeNode
{
int value;
TreeNode* parent;
TreeNode* left;
TreeNode* right;
};
struct NodeSumPair
{
TreeNode* node;
size_t sum;
NodeSumPair(TreeNode* curNode, size_t curSum)
: node(curNode)
, sum(curSum)
{}
};
std::vector<TreeNode*> FindNumOfPathsDFS(TreeNode* root, size_t sum)
{
std::stack<NodeSumPair> curStack;
size_t curSum = 0;
curStack.push(NodeSumPair(root, curSum));
std::vector<TreeNode*> result;
while (!curStack.empty()) {
const NodeSumPair& curPair = curStack.top();
if (curPair.node) {
curSum = curPair.sum + curPair.node->value;
if (curSum == sum) {
result.push_back(curPair.node);
}
// continue traversal
curStack.push(NodeSumPair(curPair.node->right, curSum));
curStack.push(NodeSumPair(curPair.node->left, curSum));
}
curStack.pop();
}
return result;
}
std::vector<TreeNode*> FindNumOfPathsBFS(TreeNode* root, size_t sum)
{
std::queue<NodeSumPair> curQueue;
size_t curSum = 0;
curQueue.push(NodeSumPair(root, curSum));
std::vector<TreeNode*> result;
while (!curQueue.empty()) {
NodeSumPair curPair = curQueue.front();
if (curPair.node) {
curSum = curPair.sum + curPair.node->value;
if (curSum == sum) {
result.push_back(curPair.node);
}
// continue traversal
curQueue.push(NodeSumPair(curPair.node->left, curSum));
curQueue.push(NodeSumPair(curPair.node->right, curSum));
}
curQueue.pop();
}
return result;
}
// ********************************************************************************
