The recursive depth-first traversal is essentially the same as the solution using a stack, it's just that you're using the call stack as the stack for the algorithm.
I love that he goes over all the common mistakes people often make on the first try! It's very normalizing to see him show those mistakes, makes me feel much better lol, and also the explanations of those mistakes dig deeper and improve our understanding.
Alvin was born to teach anything coding related I'm certain. Got introduced to him while going through app academy and everytime i see a video of his I'll watch it several times over. Ofc I try to make an independent attempt at understanding but the amount of clarity that comes from him is amazing. Thank you
I like the way you broke down the recursion problems into base cases and general cases and tackled each one independently then combined it for the final solution. I think my issue was I tried to solve it in one go which led to me getting stuck. The recursive problems can be a real head wrecker if you're not careful!!
This was a great video and very well organized. I finished watching the whole video while coding the problems on Visual Studio Code in Python and now feel I have a good grasp of BFS, DFS, especially using recursion which I struggled with before. Thank you Alvin!
it is incredible the way that you explain these challenging concepts with ease. I also watched your DP video and its amazing. Keep it going with the content
For the last problem, you could consider the null nodes as your base case but return 0 rather than negative infinity. In that way they would not contribute to the path sum, and you won't have to add leaf nodes in your base case as both paths would return your current node value + 0. However, this only works knowing that the node values are positive.
Thank you so much. It really helped me to understand the tree traversal in detail. Thanks again! I understood the DFS and BFS for the first time. Use of Queue and Stack for them is the key to understand the whole.
Alvin is my favorite tutor in free code camp, i always watch the video he make no matter what is it about. His video about dynamic programming and graph theory is really good , you guys should check it out. 👍
The topic was confusing for me and I really needed a some sort of direction to know where to start. I really appreciate this video, thank you very much man.
The max for that example is 3 however as the tree grows so does the max number so in that case it's O(h) not O(1). However this is only true in ideal conditions, if the tree was unbalanced then the height tends to approach n hence it's also fair to consider the space complexity as O(n). The worst case of such an unbalanced tree would be a linkedList looking tree for example. So both O(n) and O(h) are right, but O(h) or even O(logn) are better answers for most real binary trees.
This is an excellent video, when I sat down and really watched this thoroughly after practicing a bunch of binary tree algos, this helped to solidify even more concepts.
Great video on Binary Trees. I was struggling to solve basic problems in Binary Trees and then i finally stumbled upon this video. The way Alvin walks through the course really drills down the concept in your head and makes you feel so comfortable ! Amazing 💯
If you're doing this in python a good alternative to the spread operator is the splat operator so: def depth_search_r(root): if root is None: return [] val_left = depth_search_r(root.left) val_right= depth_search_r(root.right) return [root.val, *val_left, *val_right] #splat operator flattens list returned
Alvin is right. It's tricky to implement BFS using recurision and I did implement it - def BFS_recursive(root: Node): def myBFS(root:Node): if not root: return [] result = [] if root.left: result.append(root.left.val) if root.right: result.append(root.right.val) leftValues = myBFS(root.left) # [d,e] rightValues = myBFS(root.right) # [f] result+=(leftValues+rightValues) return result return [root.val]+myBFS(root) print('Recursive BFS output as list =>') print(BFS_recursive(a))
For the last problem (Max Root to Leaf Path Sum) I feel like writing it this way is a bit more elegant but also makes a bit more sense to me, in case it helps anyone: def max_r2l_R(root):
if(root==None): return 0
return max( root.val+max_r2l_R(root.left), root.val+max_r2l_R(root.right) ) This has ONLY 1 base case, because if you are at a leaf node, When you recursively call the function on the children you will hit the base case, which will return 0, effectively not altering your sum. This is Python, but the idea should still hold :)
Great material. 1:20:25 BinaryTree is supposed to store lower value on the left and greater on the right. private int getMin(BinaryTree bt) { if(bt == null) return -1; if(bt.left == null) return bt.val; return getMin(bt.left); }
@@suar_pilla Actually BST(Binary Search Tree) is supposed to store smaller value on the left, that doesn't apply to Binary Tree. Wording is little bit confusing
For info., In BST, there is no strict rule that less elements should go to left subtree, it's just an convention. You can make a BST where greater elements go to left and smaller go to right. You just need a partition
Hi bro! I followed the whole video until the end and finally did the last exercise by my own and it worked! Thanks for the lessons , i love you and wish you a Merry Christmas ♥
I am here to review this and boy oh boy your teaching style is making me feel like a genius again. Well you are the genius. I feel the transfer of knowledge. I didn't even need to open my editor. Just pen an paper.
do we really need to check for "null of left and right" for root to leaf? I think returning "-Infinity" would be enough because "Math.max(-Infinity,-Infinity)" already returns "-Infinity". By the way, instead of forming a tree focusing only on how to traverse tree makes this video a great resource. I didn't know traversing would be this easy since I first learned about forming the tree and it was confusing enough. Thanks again.
Great content man... Especially the animated representation of all the stuff that happens in the backend helps a lot to understand the core concept of tree data structure.
Thanks a lot dude! you made it so intuitive to solve these tree problems, just a suggestion I think last problem can be also be solved like this: function maxPathSum(node) { if (!node) return -Infinity; return node.val + Math.max(0, maxPathSum(node.left), maxPathSum(node.right)); }
This might not work. What happens when maxPathSum(node.left) and maxPathSum(node.right) evaluate to negative values, like say -5, -6? You end up returning 0. Math.max(0, -5, -6), which would be wrong
@@yonahbyarugaba AGRE but this might work def max_path_sum(root): if root == None : return 0 return root.val + max(max_path_sum(root.left), max_path_sum(root.right))
My solution to the last problem function getMaxRootToLeaf(root) { if(!root) return -Infinity; return root.value + Math.max(0, getMaxRootToLeaf(root.left), getMaxRootToLeaf(root.right)) } the check for the left node and the right node to be null is not necessary and can be replaced with comparing to zero in the min method.
00:04 Cây nhị phân thường được sử dụng trong phát triển phần mềm. 02:21 Cây nhị phân là cây mà mỗi nút có nhiều nhất hai nút con. 07:07 Cây nhị phân vẫn có thể là cây nhị phân ngay cả khi nó chỉ có một con hoặc không có nút nào. 09:25 Các bài toán về cây nhị phân rất khó nhưng có thể được xác định bằng cách làm theo ba quy tắc sau: 14:06 Độ sâu truyền tải đầu tiên của cây nhị phân 16:25 Hoạt động ngăn xếp giới hạn ở trên cùng 21:02 Triển khai giải pháp JavaScript cho vấn đề giá trị độ sâu đầu tiên 23:23 Thuật toán độ sâu đầu tiên in các nút theo thứ tự đầu tiên bên phải. 28:07 Xử lý giá trị null trong mã một cách hiệu quả 30:22 Tạo đệ quy duyệt cây theo chiều sâu 35:19 Các giá trị độ sâu đầu tiên có thể được giải quyết theo cách đệ quy hoặc lặp lại bằng cách sử dụng cấu trúc dữ liệu ngăn xếp. 37:42 Cấu trúc được thảo luận là một hàng đợi duy trì thứ tự các phần tử. 42:17 Triển khai truyền tải theo chiều rộng đầu tiên bằng cách sử dụng cấu trúc dữ liệu hàng đợi trong JavaScript 44:44 Giải pháp lặp lại cho việc truyền tải theo chiều rộng lần đầu tiên 49:27 Duyệt qua theo chiều rộng đầu tiên 51:44 Độ phức tạp về thời gian của chiến lược lặp lại theo chiều rộng là O(n) và độ phức tạp về không gian cũng là O(n). 56:30 Giải pháp JavaScript cho cây bao gồm vấn đề khi sử dụng truyền tải theo chiều rộng trước và chiều sâu đầu tiên 59:03 Mã đang duyệt cây theo thứ tự chiều rộng đầu tiên 1:03:48 Tính tổng tất cả các giá trị trong cây nhị phân 1:06:13 Giải quyết vấn đề một cách đệ quy bằng cách sử dụng phương pháp truyền tải theo chiều sâu. 1:11:19 Độ phức tạp về thời gian và không gian của giải pháp là O(n). 1:13:40 Mã đệ quy để tìm tổng của cây 1:18:25 Mã để thêm các nút con vào hàng đợi và tính tổng số tiền có thể được đơn giản hóa và cải tiến. 1:20:57 Thực hiện phương pháp lặp để tìm giá trị nhỏ nhất trong cây 1:25:24 Triển khai thuật toán truyền tải theo chiều sâu đầu tiên bằng cách sử dụng ngăn xếp trong JavaScript 1:27:44 Sử dụng một biến để theo dõi giá trị nhỏ nhất hiện tại 1:32:36 Sử dụng hàm math.min để tìm giá trị nhỏ nhất trong JavaScript 1:34:58 Tính tổng đường đi tối đa từ gốc tới lá bất kỳ. 1:39:33 Sử dụng trường hợp cơ bản là âm vô cực cho các nút null và tìm mức tối đa, chúng tôi tính toán câu trả lời cho mỗi cây con. 1:41:40 Đường dẫn từ gốc tới lá tối đa trong cây được tính toán đệ quy. 1:46:38 Mã đang gây ra lỗi do nút không đối xứng. 1:48:52 Lời khuyên phỏng vấn kỹ thuật Crafted by Merlin AI.
I just watched day before to my interview and I was called today to be hired. Going to donate full of my first salary.
Done ?
???
Sure, I’ve completed my sentence.
გამიხარდა ქართველის კომენტარი აქ და თან გამიკვირდა :დ
@@beqabeqa4955 ratom gagikvirda 😂
This guy is the best! I just wanted to brush up on this topic and stumbled upon this precious lecture. Now I want to watch all his lessons 🤓👍
The recursive depth-first traversal is essentially the same as the solution using a stack, it's just that you're using the call stack as the stack for the algorithm.
Legend is coming back again.
I love that he goes over all the common mistakes people often make on the first try! It's very normalizing to see him show those mistakes, makes me feel much better lol, and also the explanations of those mistakes dig deeper and improve our understanding.
NOT confusing explanation, soothing and clear voice, so glad I found you! great work! thanks Alvin
Alvin was born to teach anything coding related I'm certain. Got introduced to him while going through app academy and everytime i see a video of his I'll watch it several times over. Ofc I try to make an independent attempt at understanding but the amount of clarity that comes from him is amazing. Thank you
Truly ❤
I am still trying to figure out, how is he able to understand recursion so well, explain it so well, and master it so well. 🥺
repetition
I like the way you broke down the recursion problems into base cases and general cases and tackled each one independently then combined it for the final solution. I think my issue was I tried to solve it in one go which led to me getting stuck. The recursive problems can be a real head wrecker if you're not careful!!
This was a great video and very well organized. I finished watching the whole video while coding the problems on Visual Studio Code in Python and now feel I have a good grasp of BFS, DFS, especially using recursion which I struggled with before. Thank you Alvin!
did you code binary tree in python yourself? or is his code available in python somewhere
? TIA
@@kowshikthopalli866You can implement any code of any language once you have good grasp over the language you are learning
Amazing videos alvin,got the clarity of thought needed for solving problems recursively and also dynamic programming doesn't seem a giant anymore
ahh man , this is exciting to hear.
Wow, this even helped me in my lumberjack career
😂 A+
alvin is the best instructor on this channel. his voice and explanations are clear, and the animations help so much. thank you for this free education
it is incredible the way that you explain these challenging concepts with ease. I also watched your DP video and its amazing. Keep it going with the content
For the last problem, you could consider the null nodes as your base case but return 0 rather than negative infinity. In that way they would not contribute to the path sum, and you won't have to add leaf nodes in your base case as both paths would return your current node value + 0.
However, this only works knowing that the node values are positive.
Thanks! I was wondering the same thing.
yeah, just like you said, there could be negative values in the tree
This teach is the best! He really helps us visualize those abstract topics so well, which I'm sure helps a lot of people. Thank you!
What a great course! For anyone wondering, I was able to follow along in Python despite the code being in JS with minimal issues! Would recommend
Modern JS borrowed a lot from Python, at this point it’s kind of like python but with curly braces and const or let for variable declaration
These are some premium quality tutorials.
no way!!!! literally found his vids on dp and graphs last week, watching this asap.
This course is so organized and clear! Outstanding work. Thanks for sharing these lessons on youtube!
This guy is the best data structure and algorithm instructor I have known so far….
Thank you so much. It really helped me to understand the tree traversal in detail. Thanks again! I understood the DFS and BFS for the first time. Use of Queue and Stack for them is the key to understand the whole.
Alvin is my favorite tutor in free code camp, i always watch the video he make no matter what is it about. His video about dynamic programming and graph theory is really good , you guys should check it out. 👍
Yes he is very good , have you seen his dp tutorial?
@@Jitendrakumar-gb7cn ,, His video about dynamic programming and graph theory is really good"
I really enjoy this tutorials, it is go step by step rather than throw all at once.
The topic was confusing for me and I really needed a some sort of direction to know where to start. I really appreciate this video, thank you very much man.
this is such a great video for quickly getting back up to speed on trees and basic tree traversal. thank you!
Thanks Alvin for this and the dynamic programming course. They're both really helpful.
20:33 - Space complexity is actually O(h) where h = height of a tree
I don't think so. Remember the maximum number of nodes that can be on a stack at any particular time is 3, so I think it is actually O(3) === O(1)
The max for that example is 3 however as the tree grows so does the max number so in that case it's O(h) not O(1). However this is only true in ideal conditions, if the tree was unbalanced then the height tends to approach n hence it's also fair to consider the space complexity as O(n). The worst case of such an unbalanced tree would be a linkedList looking tree for example. So both O(n) and O(h) are right, but O(h) or even O(logn) are better answers for most real binary trees.
@@GrayOwl. That's a good explanation. I get you now!
Alvin is unbelievable. This is the best course on this topic. Impossible to do a better job.
This is an excellent video, when I sat down and really watched this thoroughly after practicing a bunch of binary tree algos, this helped to solidify even more concepts.
i am jus loving the fact that these are in Js
...Thankyou sir!
Great video on Binary Trees. I was struggling to solve basic problems in Binary Trees and then i finally stumbled upon this video. The way Alvin walks through the course really drills down the concept in your head and makes you feel so comfortable ! Amazing 💯
YES! Looking at the thumbnail emojis itself I knew I am gonna enjoy this video! Alvin is back!
If you're doing this in python a good alternative to the spread operator is the splat operator so:
def depth_search_r(root):
if root is None:
return []
val_left = depth_search_r(root.left)
val_right= depth_search_r(root.right)
return [root.val, *val_left, *val_right] #splat operator flattens list returned
Thanks!! Been looking for this
You can also just add lists like [root.val] + val_left + val_right
I don't comment much but man...your teaching skills are awesome. You explain like how a student want a teacher should explain to them.
💯
Really appreciate this effort. Cant express in words how he explains clearly each concept.
hey man you rocking, since 3 years i am learning data structure and algorithm.. i never feel this much understanding.
5 minutes into the video and I'm enjoying it already
Omg! You just simplified things a lot for me. So easy to understand! Awesome video!
This is my second video of yours after linked list. Really appreciated you Bro.
This explanation helped me complete a major homework. Thank you.
Alvin is right. It's tricky to implement BFS using recurision and I did implement it -
def BFS_recursive(root: Node):
def myBFS(root:Node):
if not root: return []
result = []
if root.left: result.append(root.left.val)
if root.right: result.append(root.right.val)
leftValues = myBFS(root.left) # [d,e]
rightValues = myBFS(root.right) # [f]
result+=(leftValues+rightValues)
return result
return [root.val]+myBFS(root)
print('Recursive BFS output as list =>')
print(BFS_recursive(a))
For the last problem (Max Root to Leaf Path Sum) I feel like writing it this way is a bit more elegant but also makes a bit more sense to me, in case it helps anyone:
def max_r2l_R(root):
if(root==None):
return 0
return max( root.val+max_r2l_R(root.left), root.val+max_r2l_R(root.right) )
This has ONLY 1 base case, because if you are at a leaf node, When you recursively call the function on the children you will hit the base case, which will return 0, effectively not altering your sum.
This is Python, but the idea should still hold :)
One of the best tree algo videos on YT!
Even before starting the video, I knew it's gonna be Alvin
Great material.
1:20:25 BinaryTree is supposed to store lower value on the left and greater on the right.
private int getMin(BinaryTree bt) {
if(bt == null) return -1;
if(bt.left == null) return bt.val;
return getMin(bt.left);
}
Looks like its a wrong diagram
@@suar_pilla Actually BST(Binary Search Tree) is supposed to store smaller value on the left, that doesn't apply to Binary Tree. Wording is little bit confusing
For info., In BST, there is no strict rule that less elements should go to left subtree, it's just an convention. You can make a BST where greater elements go to left and smaller go to right. You just need a partition
Your narration is great, thank you for the educontent
Hi bro! I followed the whole video until the end and finally did the last exercise by my own and it worked! Thanks for the lessons , i love you and wish you a Merry Christmas ♥
This guy is a legend, idek js but i coded it in python just by watching this video. Thank you so much for putting this gold out here for free
Well, I am 26 and, thanks to this video, recursion just clicked in my brain for the first time in my life. Thanks
i've learned lot about binary tree even half of the video , thanks lot
Alvin is the best teacher dude.
I am here to review this and boy oh boy your teaching style is making me feel like a genius again. Well you are the genius. I feel the transfer of knowledge. I didn't even need to open my editor. Just pen an paper.
This is some great content, so glad that I cam across this. Thank you for such clear tutorial
Thank You a lot Alvin for the great Course. Definitively Structy is the best place to prepare efficiently for interviews.
@Alvin, you are best, your voice and the way you explained is just fabulous.
I’m in awe of how good this guy is in every video.
It feels like all these problems are nothing; he just wrote two lines of code and it was done . he is so good
Alvin is always very clear in his concepts
Alvin is the king!! Waiting for more videos form you!
Amazing video! Thank you so much for sharing it with us. Keep up the great work.
Thank you Alvin, That was an amazing tutorial on Binary tree so far.
Great explanations ! It took me less than 5 mins to implement each :)
Dude, the way you explain this is impecable. Great job, please keep making videos like this ✌️
I was waiting for your video.. Your content is superb man.. 🔥
do we really need to check for "null of left and right" for root to leaf? I think returning "-Infinity" would be enough because "Math.max(-Infinity,-Infinity)" already returns "-Infinity".
By the way, instead of forming a tree focusing only on how to traverse tree makes this video a great resource. I didn't know traversing would be this easy since I first learned about forming the tree and it was confusing enough.
Thanks again.
this video was amazing, ty for effort
Alvin this is an excellent video. I wish you were my teacher when I started programming!
Great content man... Especially the animated representation of all the stuff that happens in the backend helps a lot to understand the core concept of tree data structure.
This is a very greate tutorial and explaination. This video describe how a programmer mind set should be when facing problems in step by step.
Thank you Alvin, now I'm a fan of recursion❤
I loved your Graph Algorithm. Could you please add more to it, more like an extension. Union find, problems like course schedule etc
This guy teaches so well
Loved that course, your teaching style is very clear and really easy to follow 💯🎉
Thanks a lot dude! you made it so intuitive to solve these tree problems, just a suggestion I think last problem can be also be solved like this:
function maxPathSum(node) {
if (!node) return -Infinity;
return node.val + Math.max(0, maxPathSum(node.left), maxPathSum(node.right));
}
That was what i thought before watching the solution
This might not work. What happens when maxPathSum(node.left) and maxPathSum(node.right) evaluate to negative values, like say -5, -6? You end up returning 0. Math.max(0, -5, -6), which would be wrong
@@yonahbyarugaba AGRE but this might work
def max_path_sum(root):
if root == None : return 0
return root.val + max(max_path_sum(root.left), max_path_sum(root.right))
Nothing short of excellent. Thanks for this video!
Not all heroes wear capes. This channel is just too good.
Thank you Programmer Alvin! Everything is very clear and easy to follow.
My solution to the last problem
function getMaxRootToLeaf(root) {
if(!root) return -Infinity;
return root.value + Math.max(0, getMaxRootToLeaf(root.left), getMaxRootToLeaf(root.right))
}
the check for the left node and the right node to be null is not necessary and can be replaced with comparing to zero in the min method.
Thank you so much for all the efforts that you put through in getting this knowledge out for free. !
Great video! Really helped me improve my knowledge of trees.
Much appreciate! It´s very clear and easy to follow!
Good video but I'd like to see step by step in debugging to make it even more clear
Thank you for this amazing course!
fantastic explanations. i would like some more information on when and where i would use these in the real world.
Alvin is the GOAT
Loved this course! Thank you for this.
2 days earlier I was just looking for this. 😂 Here we are thanks ❤❤❤
They have a hack over each and everyone's mind!
The dude is back!
You guys are simply the best. Thank you very much for these wonderful gems.
00:04 Cây nhị phân thường được sử dụng trong phát triển phần mềm.
02:21 Cây nhị phân là cây mà mỗi nút có nhiều nhất hai nút con.
07:07 Cây nhị phân vẫn có thể là cây nhị phân ngay cả khi nó chỉ có một con hoặc không có nút nào.
09:25 Các bài toán về cây nhị phân rất khó nhưng có thể được xác định bằng cách làm theo ba quy tắc sau:
14:06 Độ sâu truyền tải đầu tiên của cây nhị phân
16:25 Hoạt động ngăn xếp giới hạn ở trên cùng
21:02 Triển khai giải pháp JavaScript cho vấn đề giá trị độ sâu đầu tiên
23:23 Thuật toán độ sâu đầu tiên in các nút theo thứ tự đầu tiên bên phải.
28:07 Xử lý giá trị null trong mã một cách hiệu quả
30:22 Tạo đệ quy duyệt cây theo chiều sâu
35:19 Các giá trị độ sâu đầu tiên có thể được giải quyết theo cách đệ quy hoặc lặp lại bằng cách sử dụng cấu trúc dữ liệu ngăn xếp.
37:42 Cấu trúc được thảo luận là một hàng đợi duy trì thứ tự các phần tử.
42:17 Triển khai truyền tải theo chiều rộng đầu tiên bằng cách sử dụng cấu trúc dữ liệu hàng đợi trong JavaScript
44:44 Giải pháp lặp lại cho việc truyền tải theo chiều rộng lần đầu tiên
49:27 Duyệt qua theo chiều rộng đầu tiên
51:44 Độ phức tạp về thời gian của chiến lược lặp lại theo chiều rộng là O(n) và độ phức tạp về không gian cũng là O(n).
56:30 Giải pháp JavaScript cho cây bao gồm vấn đề khi sử dụng truyền tải theo chiều rộng trước và chiều sâu đầu tiên
59:03 Mã đang duyệt cây theo thứ tự chiều rộng đầu tiên
1:03:48 Tính tổng tất cả các giá trị trong cây nhị phân
1:06:13 Giải quyết vấn đề một cách đệ quy bằng cách sử dụng phương pháp truyền tải theo chiều sâu.
1:11:19 Độ phức tạp về thời gian và không gian của giải pháp là O(n).
1:13:40 Mã đệ quy để tìm tổng của cây
1:18:25 Mã để thêm các nút con vào hàng đợi và tính tổng số tiền có thể được đơn giản hóa và cải tiến.
1:20:57 Thực hiện phương pháp lặp để tìm giá trị nhỏ nhất trong cây
1:25:24 Triển khai thuật toán truyền tải theo chiều sâu đầu tiên bằng cách sử dụng ngăn xếp trong JavaScript
1:27:44 Sử dụng một biến để theo dõi giá trị nhỏ nhất hiện tại
1:32:36 Sử dụng hàm math.min để tìm giá trị nhỏ nhất trong JavaScript
1:34:58 Tính tổng đường đi tối đa từ gốc tới lá bất kỳ.
1:39:33 Sử dụng trường hợp cơ bản là âm vô cực cho các nút null và tìm mức tối đa, chúng tôi tính toán câu trả lời cho mỗi cây con.
1:41:40 Đường dẫn từ gốc tới lá tối đa trong cây được tính toán đệ quy.
1:46:38 Mã đang gây ra lỗi do nút không đối xứng.
1:48:52 Lời khuyên phỏng vấn kỹ thuật
Crafted by Merlin AI.
Seems useful. I am making an app with complex features and this came in just handy.
I did those three lines in one: return Math.min(root.value, treeMinValue(root.left), treeMinValue(root.right) )
Jeez. Searching for ONNLY BT and NOT BST is a hassle.
Thankfully your video actually is about BT
such a clear and helpful resource! you explain things so well!!!
It just hit my head that whole thing about BFS stack and dfs is that dfs has stack trace which is very same using stack in BFS. mind blown
Detailed Stl course with practice please!
Where were you Alvin when I was doing my Degree? Amazing content bro
This video just showed at the right time, gonna finish this. Thanks 😊
Alvin for president!