# Leetcode 112 Solution

This article provides solution to leetcode question 112 (path-sum)

https://leetcode.com/problems/path-sum

## Solution

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool hasPathSum(TreeNode* root, int sum) {
stack<TreeNode*> s;

if (root == NULL)
return false;

s.push(root);

int curr = root->val;
TreeNode* prev = NULL;
while (s.empty() == false)
{
auto p = s.top();

if (prev == NULL || (prev != p->left && prev != p->right))
{
if (p->left)
{
s.push(p->left);
curr += p->left->val;
prev = p;
}
else if (p->right)
{
s.push(p->right);
curr += p->right->val;
prev = p;
}
else
{
if (curr == sum)
return true;

prev = p;
curr -= p->val;
s.pop();
}
}
else if (prev == p->left && p->right)
{
s.push(p->right);
curr += p->right->val;
prev = p;
}
else
{
prev = p;
curr -= p->val;
s.pop();
}
}

return false;
}
};
``````