Path Sum (LeetCode 112) | Full solution with visuals and graphics | Study Algorithms

There can be so many paths in a binary tree. This video tells you how to smartly navigate the binary tree using a level order traversal technique so that you can easily determine if there is a path that has a particular sum.
Actual problem on LeetCode: leetcode.com/problems/path-sum/
Chapters:
00:00 - Intro
01:01 - Problem Statement and Description
02:42 - Finding all the possible paths (Brute Force)
04:44 - Using level order traversal smartly
09:44 - Dry-run of Code
13:54 - Final Thoughts
📚 Links to topics I talk about in the video:
Level Order Traversal: • Level order traversal ...
Recursion Algorithmic Paradigm: • Recursion paradigms wi...
Tree Data Structure: • Understanding Tree Dat...
Playlist on Trees: • Trees
📘 A text based explanation is available at: studyalgorithms.com
Code on Github: github.com/nikoo28/java-solut...
Test-cases on Github: github.com/nikoo28/java-solut...
📖 Reference Books:
Starting Learn to Code: amzn.to/36pU0JO
Favorite book to understand algorithms: amzn.to/39w3YLS
Favorite book for data structures: amzn.to/3oAVBTk
Get started for interview preparation: amzn.to/39ysbkJ
🔗 To see more videos like this, you can show your support on: www.buymeacoffee.com/studyalg...
🎥 My Recording Gear:
Recording Light: amzn.to/3pAqh8O
Microphone: amzn.to/2MCX7qU
Recording Camera: amzn.to/3alg9Ky
Tablet to sketch and draw: amzn.to/3pM6Bi4
Surface Pen: amzn.to/3pv6tTs
Laptop to edit videos: amzn.to/2LYpMqn
💻 Get Social 💻
Follow on Facebook at: / studyalgos
Follow on Twitter at: / studyalgorithms
Follow on Tumblr at: / studyalgos
Subscribe to RSS feeds: studyalgorithms.com/feed/
Join fan mail: eepurl.com/g9Dadv
#leetcode #programming #interview

[@susmitapatil4847]

Wonderful solution. He explain from basic due to which it is easy to understand. Thanks!!

[@matthewzarate8851]

I learned so much from this video! Thank you!!

[@mariapaderina5992]

Thank you, very good explanation!

[@unknownman1]

very well explained.

[@mrakshay319]

You explained with BFS and then implemented using stack, stack will use DFS as child will be added on top of sibling.

[@nikoo28]

That stack is being used to do a BFS

[@udayrajvadeghar8555]

thanks bhaiya!

[@souravhazra7592]

no need stack , you can take a pair of node and sum in queue. But well explained class Solution { bool BFS(TreeNode* root, int sum) { if(root == NULL) return false; queue que; que.push({root, root->val}); while(!que.empty()) { int parentVal = que.front().second; TreeNode* temp = que.front().first; if(parentVal == sum && temp->left == NULL && temp->right == NULL) return true; que.pop(); if(temp->left) { int cuurVal = parentVal + temp->left->val; que.push({temp->left, cuurVal}); } if(temp->right) { int cuurVal = parentVal + temp->right->val; que.push({temp->right, cuurVal}); } } return false; } public: bool hasPathSum(TreeNode* root, int sum) { return BFS(root, sum); } };

[@Viralmems_xyz]

Nice i thanks same type

[@subee128]

Thank you

[@rishikeshyadav4964]

you can use recurssion as well, here rather then adding the parent you can subtract it and send to child (the child will go ans check further) Boolean check(TreeNode A, int sum) { if(A==nulll) return false; if(A.right!=null && A.left!=null) { if(A.val == sum) return true; } return check(A.left, sum-A.val) || check(A.right,sum-A.val); }

[@fagunraythatha5601]

Amazing Video sir, I have on doubt, why arent we stopping if we see that the sum is already more than the target value and the path may have few more childs .?

[@nikoo28]

Yes, you can stop at that point but it won’t give you a lot of time benefit. The time you save will be taken up by adding the if condition to check at every step. So your time complexity will remain the same.

[@AnuragParoha-ck5ds]

Bhai ur explanation is op ❤❤❤🛐🛐🛐🛐

[@nikoo28]

Your comment makes it special 😄

[@AnuragParoha-ck5ds]

@@nikoo28 bro it's my request can you please make a video on "ninjas training" leetcode question

[@nikoo28]

@@AnuragParoha-ck5ds can you send me a link or the problem number on leetcode.

[@AnuragParoha-ck5ds]

@@nikoo28 ohkk

[@sravantipris3544]

your lectures are awesome but why you always choose BFS approach in all problems rather than DFS traversals or recursion...?

[@nikoo28]

I like doing BFS as it is easy to debug and visualize. Some problems will eventually require to use DFS for a faster approach

[@jritzeku]

I too wondered the same. I think generally, the BFS is going to be a safe bet in terms of performance. However, I still prefer recursion and go it first as safe bet and then proceed to iterative solution. Surprisingly, the iterative solutions for Binary Tree problems so far has been basically using levelOrder traversal so it isn't as bad as I though compared to the DP problems.

[@mysimplecode4608]

bro i have one doubt is the above code follow level order traversal using stack???

[@nikoo28]

Yes, it is

[@9888622400]

Thanks a lot!

[@nikoo28]

Always welcome