Path Sum - Leetcode 112 - Python

0:00 - Read the problem
1:05 - Drawing Explanation
3:25 - Coding Explanation

leetcode 112

#coding #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[hrvmhv]

Instead of adding value and maintaining current sum, you can subtract from the target. Then you can solve it without using extra helper function.

public boolean hasPathSum(TreeNode root, int targetSum) {
if(root == null) return false;
if(root.left == null && root.right == null) return targetSum - root.val == 0
return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
}

[heyyou]

Hi Neet, just wanted to thank you for this awesome channel. I started following few months back and your video on solving blind 75 for interviews helped me get a fantastic job

[stephentomaszewski]

This is preorder DFS and you don't need a helper function if you just subtract the root.val from target

class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if not root:
return False

targetSum -= root.val
if targetSum == 0 and not root.left and not root.right:
return True

return self.hasPathSum(root.left, targetSum) or self.hasPathSum(root.right, targetSum)

If you wanna solve it with iterative way, you can use DFS with two stack (one of is for iterating nodes and the other one is for to check you can reach 0 as a current total or not)

public bool HasPathSum(TreeNode root, int targetSum) {
if(root == null)
{
return false;
}

var nodes = new Stack<TreeNode>();
var sums = new Stack<int>();
nodes.Push(root);
sums.Push(targetSum - root.val);

while(nodes.Count != 0)
{
var curr = nodes.Pop();
var currSum = sums.Pop();

if(curr.left == null && curr.right == null && currSum == 0)
{
return true;
}

if(curr.left != null)
{
nodes.Push(curr.left);
sums.Push(currSum - curr.left.val);
}

if(curr.right != null)
{
nodes.Push(curr.right);
sums.Push(currSum - curr.right.val);
}

}

return false;
}

[goldtiger]

Would love it if you could go over Path Sum III at one point! It's an interesting twist on this problem.

[vipinamar]

Nice clean vid, however, this is preOrder DFS and not inOrder

[GFedya]

NeetCode! You are a real dope. Thanks a lot.

[Edmundlu]

Hell yeah! love the explanations bro. Uploaded right when i was looking for this

[datasciencetoday]

you help my soul rest after fighting countless battles.

[jshonda]

I wish I saw this. This was my interview question yesterday and I bombed it. 😭

[-Mohamed_bayan]

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if not root :
return False
if not root.left and not root.right and targetSum-root.val==0:
return True
if self.hasPathSum(root.left, targetSum-root.val):
return True
if self.hasPathSum(root.right, targetSum-root.val):
return True

return False

[versace]

When you return dfs of both left and right nodes, does the the left node dfs run and then the right runs once the left is finished?

[baby_medusa]

Hi @neetcode, for this problem, I am not seeing the backtracking step where we do something along the lines of curSum -= root.val incase we overshot.. I was kind of taking that angle and my solulution did not work. Any tips on how we can write the solution following the backtracking paradigm like the 0 value question.

[hemesh]

Hey i may sound stupid, but i still wanna clear this doubt i knew this is DFS but how come it is inorder, arent we visiting root, left and right so it shd be pre-order is not, please do correct me if I am wrong.

[shishirarora]

Is it not preorder, what you did there?

[rajarajan]

class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if root is None:
return False

if not root.left and not root.right:
return targetSum - root.val == 0

targetSum -= root.val

return self.hasPathSum(root.left, targetSum) or self.hasPathSum(root.right, targetSum)

[souljarohill]

solved on first try in 7 minutes. Were improving! I actually just updated the original function by passing in val and defaulting it to 0 if it isn't passed in. Is this bad?

[dianayao]

I'm just confused when I should use preorder, inorder or postorder?

[CS_nb]

would the memory complexity be lower if we had a nonlocal cursum variable?

[orion.]

since you visited the root node first, does it not make the traversal a pre-order