educative.io

Educative

How to solve this problem using stacks?

https://www.educative.io/courses/grokking-the-coding-interview/RMlGwgpoKKY

Hi @Shivam_Srivastav

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

Thank you


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