Hi, @Kevin Naughton Jr. your videos are extremely simple and easy to understand. Thanks for making such videos. Also, if at the end of each problem, if you could talk about the time complexity of your approach, that could also help a lot.
Cool video two advices for a more readable code 1. Given that you use return after the if, It is not needed to uses else if 2. You can use return sum === root.val instead of sum -val === 0
As you mentioned in the video that most of the problems on trees can be solved by Recursion. Is Recursion really the best method available to solve these type of questions??
There's always a tradeoff...recursive solutions are great because it oftentimes allows a complex problem to be broken down and solved rather simply (in terms of short, readable code). The downside of recursion is that it can use a lot of memory due to the recursive calls on the stack and therefore might overflow for certain inputs. It's a idea good to mention the pros and cons of using recursion during your interviews :)
Does tail-call recursion mitigate the stack overflow issue with recursion? And if so, would there then be any advantage of iterative over recursive, if recursion's main fault was offset?
Nice solution. Though we can modify 2nd if else block I believe. else if (root.left == null && root.right == null) return (sum - root.val == 0) When node doesnt have a child, we are unnecessarily increasing a call stack.
What is the time and space complexity of this method? It seems like time is O(n) but I'm not sure about space... is the space complexity O(h) where h is the height of the tree? Thanks! :)
in tree problems we always use recursion and then they ask me over the phone how to solve it recursively, and I felt like F*************************n lol
Ya, it calls on both the branches. Just think as root.left has become new root and root.val-sum is new sum. And if either one of these returns true means there is a path.
What is the time complexity of this algorithm? I have trouble finding the time complexity of recursive algorithms. I assume that since the recursive calls goes through n levels where n is the height of the algorithm, so it'd be O(log n) I think?
I believe the runtime is O(N) where N is the number of nodes in the tree. It helps me to think about it logically instead of in terms of code so maybe that will help you too. For this problem, I think to myself, "what's the worst possible scenario" to which I think the worst possible scenario is that we go through checking all the nodes in the tree but still don't manage to find a path that adds to the desired sum. So with that logic I say it's O(N). Does that make sense?
@@KevinNaughtonJr Okay, that makes more sense. Would it better to represent the number of nodes as a singular variable (N) or as a representation of the tree's height in an actual interview?
@@nealpatel7696 In my interview experience it's typical to use N to describe the number of nodes in a tree :). LMK if you have any other questions Neal!
@@KevinNaughtonJr One last one! This isn't necessarily related to this problem, though. I like using Python for interviews because of its conciseness. Since in Python, lists are used in place of arrays, can you just give a general time complexity of an algorithm regardless of how it's implemented in the specific programming language? I believe under the hood, Python lists are just vectors in C and also similar to ArrayLists in Java.
@@nealpatel7696 Yes in all my interviews I give the general time complexity of the algorithm regardless of the language...however, you should understand the language you're choosing to use. What I mean by that is understand how things work under the hood. So in Java is I use the "contains" method I need to understand that that will perform a linear scan of my elements looking for a specific element. My point being that you can degrade your runtime if you don't understand the consequences of using certain functions in your language...so a solution that I thought was O(n) might become O(n * m) because of a function I choose to use. I hope that makes sense, if it doesn't lmk and I can explain more :)
Thank you for the video. For anyone looking for a python solution def path_sum(root, value): if not root: return stack = [] stack.append([root, value-root.data]) while value != 0 and stack: node, rsum = stack.pop() if rsum == 0: return True if node.right: stack.append([node.right, rsum - node.right.data]) if node.left: stack.append([node.left, rsum - node.left.data]) return False
Your logics and explanations are so clear Kevin.They are of great help for the beginners.A big THANK YOU :)
Wow that sound of the keystrokes :)
Hi, @Kevin Naughton Jr. your videos are extremely simple and easy to understand. Thanks for making such videos. Also, if at the end of each problem, if you could talk about the time complexity of your approach, that could also help a lot.
SANA JAHAN thanks Sana I really appreciate it! In more recent videos I talk about time and space complexity at the end :)
@@KevinNaughtonJr Hi, would you please also do some videos on sliding window concept related problems:)? Thanks.
@@sanajahan1275
See medium article by Saurabh Medhapati .it is like gem for sliding window
@@goodpeople7615 can you pls send the link I can't find it out
You're awesome man
Cool video
two advices for a more readable code
1. Given that you use return after the if, It is not needed to uses else if
2. You can use return sum === root.val instead of sum -val === 0
nope, I think it's readable for me
As you mentioned in the video that most of the problems on trees can be solved by Recursion. Is Recursion really the best method available to solve these type of questions??
There's always a tradeoff...recursive solutions are great because it oftentimes allows a complex problem to be broken down and solved rather simply (in terms of short, readable code). The downside of recursion is that it can use a lot of memory due to the recursive calls on the stack and therefore might overflow for certain inputs. It's a idea good to mention the pros and cons of using recursion during your interviews :)
Does tail-call recursion mitigate the stack overflow issue with recursion? And if so, would there then be any advantage of iterative over recursive, if recursion's main fault was offset?
The best and easiest solution! Thank you
This logic is awesome !!! I was like writing lot of if conditions n loops.... How can you think of such crisp solution ??
Nice solution. Though we can modify 2nd if else block I believe.
else if (root.left == null && root.right == null) return (sum - root.val == 0)
When node doesnt have a child, we are unnecessarily increasing a call stack.
I was trying to solve it as BFS and Dynamic Programming solution.. I thought too much tho
Best solutions in the net. hands down
Difference in logic in dp when you have to return true/false vs when you return some structure
Great explanation! Thanks!
This seems like your just going down the left and right is that correct
What is the time and space complexity of this method? It seems like time is O(n) but I'm not sure about space... is the space complexity O(h) where h is the height of the tree? Thanks! :)
Auxiliary space complexity due to recursion on the worst case is O(n) and I think no other extra space is used.
in tree problems we always use recursion and then they ask me over the phone how to solve it recursively, and I felt like F*************************n lol
nice & clean explanation
thanks!
Clean and nice explanation. Thanks.
is there any iterative approach for this question?
why does no one know how to do the iterative approach to this problem.
thanks dear bro
Can I reduce the recursion by adding a negative check on sum?
Can someone explain why in the return statement there is || operator and not && . We want both left and right to be called right?
hasPathSum(root.left, ...) || hasPathSum(root.right, ... )
I don't know what does this code call, recursive call on both branches or something else?
Ya, it calls on both the branches. Just think as root.left has become new root and root.val-sum is new sum. And if either one of these returns true means there is a path.
It keeps go down to the end see if one end return true....
You are a God
What is the time complexity of this algorithm? I have trouble finding the time complexity of recursive algorithms. I assume that since the recursive calls goes through n levels where n is the height of the algorithm, so it'd be O(log n) I think?
I believe the runtime is O(N) where N is the number of nodes in the tree. It helps me to think about it logically instead of in terms of code so maybe that will help you too. For this problem, I think to myself, "what's the worst possible scenario" to which I think the worst possible scenario is that we go through checking all the nodes in the tree but still don't manage to find a path that adds to the desired sum. So with that logic I say it's O(N). Does that make sense?
@@KevinNaughtonJr Okay, that makes more sense. Would it better to represent the number of nodes as a singular variable (N) or as a representation of the tree's height in an actual interview?
@@nealpatel7696 In my interview experience it's typical to use N to describe the number of nodes in a tree :). LMK if you have any other questions Neal!
@@KevinNaughtonJr One last one! This isn't necessarily related to this problem, though. I like using Python for interviews because of its conciseness. Since in Python, lists are used in place of arrays, can you just give a general time complexity of an algorithm regardless of how it's implemented in the specific programming language? I believe under the hood, Python lists are just vectors in C and also similar to ArrayLists in Java.
@@nealpatel7696 Yes in all my interviews I give the general time complexity of the algorithm regardless of the language...however, you should understand the language you're choosing to use. What I mean by that is understand how things work under the hood. So in Java is I use the "contains" method I need to understand that that will perform a linear scan of my elements looking for a specific element. My point being that you can degrade your runtime if you don't understand the consequences of using certain functions in your language...so a solution that I thought was O(n) might become O(n * m) because of a function I choose to use. I hope that makes sense, if it doesn't lmk and I can explain more :)
really simple explanation ver nic
Thanks so much happy to hear the explanations are helpful!
class Solution
{
public boolean hasPathSum(TreeNode root, int k)
{
if(root==null)
{
return false;
}
if(root.left==null && root.right==null && k-root.val==0)
{
return true;
}
boolean leftCall=hasPathSum(root.left,k-root.val);
boolean rightCall=hasPathSum(root.right,k-root.val);
return leftCall || rightCall;
}
}
ty
Anytime thank YOU for the support!
Thank you for the video. For anyone looking for a python solution
def path_sum(root, value):
if not root:
return
stack = []
stack.append([root, value-root.data])
while value != 0 and stack:
node, rsum = stack.pop()
if rsum == 0:
return True
if node.right:
stack.append([node.right, rsum - node.right.data])
if node.left:
stack.append([node.left, rsum - node.left.data])
return False
THANK U, NEXT
Yi Cai NO PROBLEM