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.
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 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.
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!!
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))
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
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 :)
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.
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.
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 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. 👍
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.
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.
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.
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.
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.
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 💯
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 implemented iterative BFS using Stack as well as Queue in Python - # Iterative BFS using Stack def BFS(root: Node): if not root: return [] result = [] stack = [root] while len(stack)>0: current = stack.pop() if current: if current.right: stack.append(current.right) if current.left: stack.append(current.left) if current.left: result.append(current.left.val) if current.right: result.append(current.right.val) return [root.val] + result print('Iterative BFS output as list =>') print(BFS(a)) # Iterative BFS using Queue from collections import deque def BFS_queue(root: Node): if not root: return [] queue = deque() queue.append(root) result = [] while len(queue)>0: current = queue.popleft() if current: result.append(current.val) queue.append(current.left) queue.append(current.right) return result print('Iterative BFS output as list =>') print(BFS_queue(a))
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 ♥
You have a gift for explaining things, I will advise to work a bit on your presentation habits to remove the world filler such as "right, here, etc" and you will take your presentation to the next level!
🎯 Key Takeaways for quick navigation: - Overview of the course covering both theory and practical aspects of binary tree algorithms. - Whiteboard visualization and code implementation for each algorithm. 01:25 🌲 *Understanding Trees* - Introduction to the concept of trees in programming. - Nodes, edges, and the familial relationship between nodes. 02:49 👨👧👦 *Family Relationships in Trees* - Exploring family relationships within trees. - Using familial terms (parent, child) to describe relationships between nodes. 04:09 🌳 *Basics of Binary Trees* - Definition of a binary tree: Each node has at most two children. - Criteria for a binary tree: At most two children, a single root, and a unique path from root to any node. 05:34 🔄 *Generalizing Leaf Nodes* - Generalizing the concept of leaf nodes in a binary tree. - Emphasis on understanding a leaf node based on the absence of children. 06:56 🌳 *Edge Cases in Binary Trees* - Exploration of edge cases in binary trees. - Examples of valid binary trees with one node, empty trees, and trees with different structures. 08:19 🚫 *Invalid Binary Trees* - Identification of invalid binary trees based on criteria violations. - Analysis of examples where nodes have multiple parents or cycles exist in the structure. 09:38 🧠 *Recognizing Binary Tree Patterns* - The importance of recognizing binary tree patterns in problem-solving during interviews. - Solving problems where the data structure is not explicitly mentioned. 10:36 💻 *Representing Binary Trees Programmatically* - Introduction to representing binary trees programmatically using classes. - Creation of a `Node` class in JavaScript to store values and child pointers. 11:59 🛠️ *Hands-On Coding for Binary Trees* - Practical demonstration of coding a simple binary tree representation in JavaScript. - Creating instances of the `Node` class and establishing connections between nodes. 14:22 🧭 *Depth-First Traversal Algorithm* - Introduction to the depth-first traversal algorithm. - Explanation of how depth-first traversal follows a specific order in exploring nodes. 16:36 📚 *Stack-based Implementation for Depth-First Traversal* - Understanding how a stack data structure is used for depth-first traversal. - Explanation of stack characteristics: adding and removing elements from the top. 17:04 🌲 *Depth First Traversal Introduction* - Explanation of the initial setup for depth-first traversal using a stack. - Key actions include checking if the stack is empty, popping the top element, and exploring its children. 18:00 🔄 *Iterative Depth First Traversal* - Walkthrough of the iterative implementation of depth-first traversal. - Demonstration of pushing children onto the stack based on left and right nodes. 19:51 ⏰ *Time and Space Complexity Analysis* - Explanation of time and space complexity analysis for the iterative depth-first traversal. - Time complexity analyzed as O(n) due to visiting each node once. 21:06 📜 *Introduction to Recursive Solution* - Transition from iterative to recursive solution. - Definition of the base case for an empty tree. 22:33 🔍 *Recursive Implementation - Part 1* - Recursive leap of faith: explanation of recursive calls for left and right subtrees. - Introduction of variables to store results from recursive calls. 26:44 🐞 *Handling Edge Case* - Identification and resolution of an edge case where the root is null. - Addition of a guard clause to handle the scenario of an empty tree. 29:07 🔄 *Recursive Implementation - Part 2* - Continuation of the recursive implementation. - Explanation of combining values with the root and results from left and right subtrees. How does *the use of a stack contribute to the efficiency of the iterative depth-first traversal?* Can you *provide an example where a different tree structure might affect the order of traversal in the recursive solution?* In scenarios *where the tree is extremely large, how might memory limitations impact the performance of the depth-first traversal algorithms?* 34:35 🧠 *Depth First Traversal using Stack* - Demonstrates depth-first traversal using stack and spread syntax. - Explains the stack data structure for iterative depth-first traversal. 36:07 🌐 *Breadth First Traversal Overview* - Introduces the breadth-first traversal concept. - Describes the breadth-first order in contrast to depth-first. 37:27 🔄 *Implementing Breadth First Traversal* - Details the iterative implementation of breadth-first traversal. - Explains the use of a queue and its FIFO nature. 40:42 📉 *Time and Space Complexity of Breadth First Traversal* - Discusses the time complexity of breadth-first traversal. - Considers the space complexity, emphasizing queue operations. 42:12 🖥️ *JavaScript Solution for Breadth First Traversal* - Walks through the JavaScript code for breadth-first traversal. - Utilizes an array as a queue for an iterative solution. 47:46 🎯 *Preparing for Tree Includes Problem* - Introduces the "tree includes" problem. - Outlines the task of determining if a target value exists in a binary tree. 51:39 📊 *Complexity Analysis of Breadth-First Search* - Analyzes the time and space complexity of iterative breadth-first search. - Considers the linear time complexity based on node additions and removals. How does *the use of spread syntax simplify the implementation of depth-first traversal?* Can you *provide examples of scenarios where depth-first traversal might be preferable over breadth-first traversal?* In the *breadth-first traversal JavaScript solution, how would the code need to be adjusted if the order of traversal needed to be right to left instead of left to right?* 52:34 🌳 *Recursive Depth-First Approach for Tree Search* - Recursive depth-first solution for tree search 56:40 🧠 *Logical OR in Recursive Solution* - Using logical OR to combine Boolean values in recursive calls 57:12 🖥️ *Iterative Breadth-First Search for Tree Search* - Implementation of iterative breadth-first search 01:02:36 🌲 *Recursive Depth-First Approach Implementation* - Recursive depth-first implementation for tree search 01:05:53 🔄 *Importance of Base Case Ordering* - Emphasizing the importance of base case ordering 01:09:32 📊 *Recursive Tree Sum Problem* - Recursive approach for calculating the total sum of a binary tree 01:10:30 🌳 *Recursive Algorithm for Binary Tree Sum* - Recursive algorithms for binary trees involve base cases and computation based on children's answers. 01:12:19 🖥️ *Walkthrough of JavaScript Solution for Tree Sum* - Walkthrough of the JavaScript solution for the tree sum problem. 01:19:57 🌲 *Tree Min Value Problem Approach* - Approach for solving the tree min value problem using either breadth-first or depth-first traversal. 01:25:33 🧮 *JavaScript Solution for Tree Min Value* - JavaScript solution for the tree min value problem. How does *the use of positive infinity for null nodes simplify the logic in recursive tree algorithms?* Can you *explain the rationale behind choosing positive infinity as the default value for tracking the minimum in the tree min value problem?* In the *iterative solution, what considerations should be made when choosing between depth-first and breadth-first traversal for binary tree problems?* 01:28:11 🌲 *Iterative Depth-First Traversal for Minimum Value in Binary Tree* - Choosing a default value for the smallest variable, like positive infinity, is a common pattern. 01:29:39 🌐 *Breadth-First Traversal for Minimum Value in Binary Tree* - Switching from depth-first to breadth-first is achieved by using `stack.shift()` for the queue. 01:31:05 🔃 *Recursive Depth-First Traversal for Minimum Value in Binary Tree* - Recursive depth-first traversal is implemented for finding the minimum value in a binary tree. 01:34:19 🌳 *Introduction to Max Root to Leaf Path Sum Problem* - The problem of finding the maximum root to leaf path sum in a binary tree is introduced. 01:34:46 🧠 *Analyzing Paths in Binary Tree* - Understanding the concept of root to leaf paths in a binary tree. 01:37:10 🔍 *Recursive Approach for Max Root to Leaf Path Sum* 01:43:50 🖥️ *JavaScript Implementation of Max Root to Leaf Path Sum* - Translating the recursive approach into JavaScript code for finding the max root to leaf path sum. How does *the choice of default values (like positive infinity) contribute to the efficiency of algorithms in tree traversal?* In what *scenarios would you prefer recursive solutions over iterative ones when dealing with binary tree problems?* How could *you modify the max root to leaf path sum algorithm to also identify and print the specific path that yields the maximum sum?* 01:45:39 🔄 *Max Path Sum Recursive Implementation* - Recursive implementation to find the maximum root-to-leaf path sum. 01:46:38 🐞 *Error Handling for Asymmetric Nodes* - Identifies and addresses an error caused by asymmetric nodes (nodes with no left child). 01:48:07 🛠️ *Conclusion and Recap* - Concludes the course on the introduction to binary trees. Made with HARPA AI
20:50 DFT Time O(N) and Space O(N) complexities. 41:07 BFT Time O(N) and Space O(N) complexities. 52:16 Tree Includes Time O(N) and Space O(N) complexities. 1:11:52 Tree Sum Time O(N) and Space O(N) complexities. 1:25:21 Tree Min value Time O(N) and Space O(N) complexities. 1:42:56 Tree Min value Time O(N) and Space O(N) complexities.
for guarding the root is null situation, I am thinking root?.val === target, would also work and made the condition check code into a single line. Not sure if it's not a preferable way because of some reasons that I am not aware of though.
In the cycle example, it makes sense that there isn't necessarily 1 root. However, I'm not sure if the "exactly 1 path" is violated. I understand the infinite paths, but is it not enough to get to the desired node the first time? In other words, are we looking only at traversal possibilities and not the fact that traversal after finding the node is just a waste of time?
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 😂
NOT confusing explanation, soothing and clear voice, so glad I found you! great work! thanks Alvin
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.
Yes but i think calling function will use more momery and time .
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 🤓👍
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 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.
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!!
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))
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
This guy is the best data structure and algorithm instructor I have known so far….
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 :)
no way!!!! literally found his vids on dp and graphs last week, watching this asap.
Legend is coming back again.
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!
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
Alvin is unbelievable. This is the best course on this topic. Impossible to do a better job.
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 feels like all these problems are nothing; he just wrote two lines of code and it was done . he is so good
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
I really enjoy this tutorials, it is go step by step rather than throw all at once.
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
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.
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
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 prefer solving graph algorithms (tree, dfs,bfs ... ) by usimg stack,it is so friendly compare to recursive
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.
💯
One of the best tree algo videos on YT!
this is such a great video for quickly getting back up to speed on trees and basic tree traversal. thank you!
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"
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.
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
This course is so organized and clear! Outstanding work. Thanks for sharing these lessons on youtube!
These are some premium quality tutorials.
i am jus loving the fact that these are in Js
...Thankyou sir!
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.
5 minutes into the video and I'm enjoying it already
Thanks Alvin for this and the dynamic programming course. They're both really helpful.
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.
This explanation helped me complete a major homework. Thank you.
Really appreciate this effort. Cant express in words how he explains clearly each concept.
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 my second video of yours after linked list. Really appreciated you Bro.
YES! Looking at the thumbnail emojis itself I knew I am gonna enjoy this video! Alvin is back!
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!
hey man you rocking, since 3 years i am learning data structure and algorithm.. i never feel this much understanding.
Jeez. Searching for ONNLY BT and NOT BST is a hassle.
Thankfully your video actually is about BT
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.
I did those three lines in one: return Math.min(root.value, treeMinValue(root.left), treeMinValue(root.right) )
Alvin is the best teacher dude.
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 💯
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.
Wow, this even helped me in my lumberjack career
😂 A+
I’m in awe of how good this guy is in every video.
Alvin is always very clear in his concepts
@Alvin, you are best, your voice and the way you explained is just fabulous.
Even before starting the video, I knew it's gonna be Alvin
This guy teaches so well
I implemented iterative BFS using Stack as well as Queue in Python -
# Iterative BFS using Stack
def BFS(root: Node):
if not root: return []
result = []
stack = [root]
while len(stack)>0:
current = stack.pop()
if current:
if current.right: stack.append(current.right)
if current.left: stack.append(current.left)
if current.left:
result.append(current.left.val)
if current.right:
result.append(current.right.val)
return [root.val] + result
print('Iterative BFS output as list =>')
print(BFS(a))
# Iterative BFS using Queue
from collections import deque
def BFS_queue(root: Node):
if not root: return []
queue = deque()
queue.append(root)
result = []
while len(queue)>0:
current = queue.popleft()
if current:
result.append(current.val)
queue.append(current.left)
queue.append(current.right)
return result
print('Iterative BFS output as list =>')
print(BFS_queue(a))
Omg! You just simplified things a lot for me. So easy to understand! Awesome video!
Alvin is the king!! Waiting for more videos form you!
1:19:40 some philosophical stuff here
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
1:19:33 - "Eventually, everything's gonna leave. Right?"
Yes, Alvin. I feel you..
i've learned lot about binary tree even half of the video , thanks lot
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 video was amazing, ty for effort
Alvin is the GOAT
Alvin = immediate upvote.
You have a gift for explaining things, I will advise to work a bit on your presentation habits to remove the world filler such as "right, here, etc" and you will take your presentation to the next level!
alvin, the best tutor ever
Well, I am 26 and, thanks to this video, recursion just clicked in my brain for the first time in my life. Thanks
Your narration is great, thank you for the educontent
Thank you Alvin, now I'm a fan of recursion❤
Thank You a lot Alvin for the great Course. Definitively Structy is the best place to prepare efficiently for interviews.
Not all heroes wear capes. This channel is just too good.
Dude, the way you explain this is impecable. Great job, please keep making videos like this ✌️
Great explanations ! It took me less than 5 mins to implement each :)
Amazing video! Thank you so much for sharing it with us. Keep up the great work.
🎯 Key Takeaways for quick navigation:
- Overview of the course covering both theory and practical aspects of binary tree algorithms.
- Whiteboard visualization and code implementation for each algorithm.
01:25 🌲 *Understanding Trees*
- Introduction to the concept of trees in programming.
- Nodes, edges, and the familial relationship between nodes.
02:49 👨👧👦 *Family Relationships in Trees*
- Exploring family relationships within trees.
- Using familial terms (parent, child) to describe relationships between nodes.
04:09 🌳 *Basics of Binary Trees*
- Definition of a binary tree: Each node has at most two children.
- Criteria for a binary tree: At most two children, a single root, and a unique path from root to any node.
05:34 🔄 *Generalizing Leaf Nodes*
- Generalizing the concept of leaf nodes in a binary tree.
- Emphasis on understanding a leaf node based on the absence of children.
06:56 🌳 *Edge Cases in Binary Trees*
- Exploration of edge cases in binary trees.
- Examples of valid binary trees with one node, empty trees, and trees with different structures.
08:19 🚫 *Invalid Binary Trees*
- Identification of invalid binary trees based on criteria violations.
- Analysis of examples where nodes have multiple parents or cycles exist in the structure.
09:38 🧠 *Recognizing Binary Tree Patterns*
- The importance of recognizing binary tree patterns in problem-solving during interviews.
- Solving problems where the data structure is not explicitly mentioned.
10:36 💻 *Representing Binary Trees Programmatically*
- Introduction to representing binary trees programmatically using classes.
- Creation of a `Node` class in JavaScript to store values and child pointers.
11:59 🛠️ *Hands-On Coding for Binary Trees*
- Practical demonstration of coding a simple binary tree representation in JavaScript.
- Creating instances of the `Node` class and establishing connections between nodes.
14:22 🧭 *Depth-First Traversal Algorithm*
- Introduction to the depth-first traversal algorithm.
- Explanation of how depth-first traversal follows a specific order in exploring nodes.
16:36 📚 *Stack-based Implementation for Depth-First Traversal*
- Understanding how a stack data structure is used for depth-first traversal.
- Explanation of stack characteristics: adding and removing elements from the top.
17:04 🌲 *Depth First Traversal Introduction*
- Explanation of the initial setup for depth-first traversal using a stack.
- Key actions include checking if the stack is empty, popping the top element, and exploring its children.
18:00 🔄 *Iterative Depth First Traversal*
- Walkthrough of the iterative implementation of depth-first traversal.
- Demonstration of pushing children onto the stack based on left and right nodes.
19:51 ⏰ *Time and Space Complexity Analysis*
- Explanation of time and space complexity analysis for the iterative depth-first traversal.
- Time complexity analyzed as O(n) due to visiting each node once.
21:06 📜 *Introduction to Recursive Solution*
- Transition from iterative to recursive solution.
- Definition of the base case for an empty tree.
22:33 🔍 *Recursive Implementation - Part 1*
- Recursive leap of faith: explanation of recursive calls for left and right subtrees.
- Introduction of variables to store results from recursive calls.
26:44 🐞 *Handling Edge Case*
- Identification and resolution of an edge case where the root is null.
- Addition of a guard clause to handle the scenario of an empty tree.
29:07 🔄 *Recursive Implementation - Part 2*
- Continuation of the recursive implementation.
- Explanation of combining values with the root and results from left and right subtrees.
How does *the use of a stack contribute to the efficiency of the iterative depth-first traversal?*
Can you *provide an example where a different tree structure might affect the order of traversal in the recursive solution?*
In scenarios *where the tree is extremely large, how might memory limitations impact the performance of the depth-first traversal algorithms?*
34:35 🧠 *Depth First Traversal using Stack*
- Demonstrates depth-first traversal using stack and spread syntax.
- Explains the stack data structure for iterative depth-first traversal.
36:07 🌐 *Breadth First Traversal Overview*
- Introduces the breadth-first traversal concept.
- Describes the breadth-first order in contrast to depth-first.
37:27 🔄 *Implementing Breadth First Traversal*
- Details the iterative implementation of breadth-first traversal.
- Explains the use of a queue and its FIFO nature.
40:42 📉 *Time and Space Complexity of Breadth First Traversal*
- Discusses the time complexity of breadth-first traversal.
- Considers the space complexity, emphasizing queue operations.
42:12 🖥️ *JavaScript Solution for Breadth First Traversal*
- Walks through the JavaScript code for breadth-first traversal.
- Utilizes an array as a queue for an iterative solution.
47:46 🎯 *Preparing for Tree Includes Problem*
- Introduces the "tree includes" problem.
- Outlines the task of determining if a target value exists in a binary tree.
51:39 📊 *Complexity Analysis of Breadth-First Search*
- Analyzes the time and space complexity of iterative breadth-first search.
- Considers the linear time complexity based on node additions and removals.
How does *the use of spread syntax simplify the implementation of depth-first traversal?*
Can you *provide examples of scenarios where depth-first traversal might be preferable over breadth-first traversal?*
In the *breadth-first traversal JavaScript solution, how would the code need to be adjusted if the order of traversal needed to be right to left instead of left to right?*
52:34 🌳 *Recursive Depth-First Approach for Tree Search*
- Recursive depth-first solution for tree search
56:40 🧠 *Logical OR in Recursive Solution*
- Using logical OR to combine Boolean values in recursive calls
57:12 🖥️ *Iterative Breadth-First Search for Tree Search*
- Implementation of iterative breadth-first search
01:02:36 🌲 *Recursive Depth-First Approach Implementation*
- Recursive depth-first implementation for tree search
01:05:53 🔄 *Importance of Base Case Ordering*
- Emphasizing the importance of base case ordering
01:09:32 📊 *Recursive Tree Sum Problem*
- Recursive approach for calculating the total sum of a binary tree
01:10:30 🌳 *Recursive Algorithm for Binary Tree Sum*
- Recursive algorithms for binary trees involve base cases and computation based on children's answers.
01:12:19 🖥️ *Walkthrough of JavaScript Solution for Tree Sum*
- Walkthrough of the JavaScript solution for the tree sum problem.
01:19:57 🌲 *Tree Min Value Problem Approach*
- Approach for solving the tree min value problem using either breadth-first or depth-first traversal.
01:25:33 🧮 *JavaScript Solution for Tree Min Value*
- JavaScript solution for the tree min value problem.
How does *the use of positive infinity for null nodes simplify the logic in recursive tree algorithms?*
Can you *explain the rationale behind choosing positive infinity as the default value for tracking the minimum in the tree min value problem?*
In the *iterative solution, what considerations should be made when choosing between depth-first and breadth-first traversal for binary tree problems?*
01:28:11 🌲 *Iterative Depth-First Traversal for Minimum Value in Binary Tree*
- Choosing a default value for the smallest variable, like positive infinity, is a common pattern.
01:29:39 🌐 *Breadth-First Traversal for Minimum Value in Binary Tree*
- Switching from depth-first to breadth-first is achieved by using `stack.shift()` for the queue.
01:31:05 🔃 *Recursive Depth-First Traversal for Minimum Value in Binary Tree*
- Recursive depth-first traversal is implemented for finding the minimum value in a binary tree.
01:34:19 🌳 *Introduction to Max Root to Leaf Path Sum Problem*
- The problem of finding the maximum root to leaf path sum in a binary tree is introduced.
01:34:46 🧠 *Analyzing Paths in Binary Tree*
- Understanding the concept of root to leaf paths in a binary tree.
01:37:10 🔍 *Recursive Approach for Max Root to Leaf Path Sum*
01:43:50 🖥️ *JavaScript Implementation of Max Root to Leaf Path Sum*
- Translating the recursive approach into JavaScript code for finding the max root to leaf path sum.
How does *the choice of default values (like positive infinity) contribute to the efficiency of algorithms in tree traversal?*
In what *scenarios would you prefer recursive solutions over iterative ones when dealing with binary tree problems?*
How could *you modify the max root to leaf path sum algorithm to also identify and print the specific path that yields the maximum sum?*
01:45:39 🔄 *Max Path Sum Recursive Implementation*
- Recursive implementation to find the maximum root-to-leaf path sum.
01:46:38 🐞 *Error Handling for Asymmetric Nodes*
- Identifies and addresses an error caused by asymmetric nodes (nodes with no left child).
01:48:07 🛠️ *Conclusion and Recap*
- Concludes the course on the introduction to binary trees.
Made with HARPA AI
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.
20:50 DFT Time O(N) and Space O(N) complexities. 41:07 BFT Time O(N) and Space O(N) complexities. 52:16 Tree Includes Time O(N) and Space O(N) complexities. 1:11:52 Tree Sum Time O(N) and Space O(N) complexities. 1:25:21 Tree Min value Time O(N) and Space O(N) complexities. 1:42:56 Tree Min value Time O(N) and Space O(N) complexities.
Alvin for president!
solution of lastone
const minSumOfPath=(root)=>{
if(root==null) return 0;
let leftNode=minSumOfPath(root.left)
let rightNode=minSumOfPath(root.right)
return Math.max(root.val+leftNode,root.val+rightNode)
}
console.log(minSumOfPath(a))
Alvin is back in the game!!!!
The shift operation runs in O(n) time. Why is your breadth first example running in O(n) instead of O(n^2) ?
Thank you Programmer Alvin! Everything is very clear and easy to follow.
This is some great content, so glad that I cam across this. Thank you for such clear tutorial
for guarding the root is null situation, I am thinking root?.val === target, would also work and made the condition check code into a single line. Not sure if it's not a preferable way because of some reasons that I am not aware of though.
After watch 50+ video on tree i gaot this which one is best to understand and clear my concept
Thank you Alvin, That was an amazing tutorial on Binary tree so far.
The dude is back!
Nothing short of excellent. Thanks for this video!
very soothing voice... good explanations as well
Thank you for this amazing course!
Good video but I'd like to see step by step in debugging to make it even more clear
This is golden!
In the cycle example, it makes sense that there isn't necessarily 1 root.
However, I'm not sure if the "exactly 1 path" is violated.
I understand the infinite paths, but is it not enough to get to the desired node the first time?
In other words, are we looking only at traversal possibilities and not the fact that traversal after finding the node is just a waste of time?
Alvin, you are the best. Thank you
Had to do a double-take. I was like, "hey isn't that the guy from App Academy?" lol
best explanation of dfs thank you