https://www.educative.io/courses/grokking-the-coding-interview/RMlGwgpoKKY
Please note that the current solution also uses a stack. It’s a recursive solution and recursion is nothing but function calls, and we know that function calls are handled by the compiler using a stack.
If you want to view an iterative solution using Stack in C++ STL, you can have a look at the following code:
static bool hasPath(TreeNode *root, int sum) {
stack<TreeNode*> nodes;
nodes.push(root);
stack<int> sums;
sums.push(sum-root->val);
while(!nodes.empty()){
TreeNode *curr=nodes.top();
nodes.pop();
int remainingSum=sums.top();
sums.pop();
if(remainingSum==0 && curr->left==nullptr && curr->right==nullptr)
return true;
if(curr->left!=nullptr && remainingSum-curr->left->val>=0){
nodes.push(curr->left);
sums.push(remainingSum-curr->left->val);
}
if(curr->right!=nullptr && remainingSum-curr->right->val>=0){
nodes.push(curr->right);
sums.push(remainingSum-curr->right->val);
}
}
return false;
}
2 Likes
pushing right child on stack last will mean right node will be processed before the left.
Course: Grokking the Coding Interview: Patterns for Coding Questions - Learn Interactively
Lesson: Binary Tree Path Sum (easy) - Grokking the Coding Interview: Patterns for Coding Questions