be careful tho. A lot of people overuse recursion because they wanna be fancy. But remember, recursion builds a stack in memory and does not release it until it works it's way back to the first call. This could lead to some issues. Most things that people use recursion for can be easily done with a simple loop.
I would have expected the insert and contains functions to be in a Tree class of some sort, and the node to be an internal implementation operating on a comparable interface. So we can return just the data not the node itself. I know it's outside of the scope of this video, but wondering if it's a common practice to put this logic inside of the node class.
Very well explained. I found how you visually grouped the "paths" of recursive calls helpful to understand what was happening when "traversing" the tree.
2 Questions: method printInOrder() what is System.out.printIn(data) doing? Also in this in-order example.. why after 5 is the next “in-order” number 8? Shouldn’t it be 10? I understand recursively we’re traversing to the Left most depth node in the binary tree ( up until left == null ) - but I’m confused how we’re printing from that point forward.
it is called as, public static void main(String[] args) { //Say you have a tree with root node being "root" int value = 6; if(root!=null) { root.insert(value); } }
Thanks for the video. But IMO there is an issue with how the code is written since these methods are operations on the tree data structure, not the node data structure, hence they should be located inside the respective ADT. Apart from that, the code looks great and is easy to understand. Great work!
@kicksomeup6998 you mean that each individual node does not contain a node data instance variable? Or that the contains() method is not written as an instance non static method within the node class?
Very excellent explanation, clearest one I’ve ever heard. Deleting needs its own video, so I understand why you decided not to include it. On programming tests, I’m always like “can I not write out all the recursion methods? I hate writing all the if statements... we both know what we are talking about, this is a binary search tree ok?” haha.
I was confused as to how 10 gets printed before 5,8. But it's more like, if root has something then do printInOrder of left & 'AFTER' left.printInOrder (which is recursive in itself). print the node itself. So basically the ENTIRE tree on the left of every node gets printed first...Then the root of every subtree, then then the right and finally the ENTIRE subtree of the right
I think this is cleaner... but is it better/worse? (Its C++, if any wonder) bool contains(int value){ if(this == nullptr) return false; else if(value == data) return true; else if(valuecontains(value); else if(value>data) return right->contains(value); return false; }
Another way would be to create a Node class as an inner class of Tree class and provide insert, delete, traversal methods within Tree class instead of Node class. I found this approach better from OO Design perspective but slightly more complex and difficult to present during a coding interview.
I recently got an assignment of a BST with satellite information on each node. I haven't found anywhere any information about this. Would you please do one about this. I am taking an algorithms class.
Honestly, after watching this video I got confused. I am sure that this code works fine, but why is there no Binary Tree structure being created? All the functions which ideally should be written for a BST data structure are written for a node. So if I wanted to construct a BST, do I create a Node object??
Very nice little lecture, but I cannot figure it out which would be an example of a good real developer scenario in which a tree would be the more efficient way.
I followed her steps on the printInOrder() method up until the 8, but then when she said 10 prints next, and then 15, she really lost me, I just don't see how it worked with the recursion. Can anyone help break it down into steps?
So basically, what you are doing here is looking if left exists, because presumably when it doesn't, you are at the top most element, which in this case, will be the smallest. If you write out the code and step through in a debugger, we use the last inserted left. When we see that this left isn't null, we call the function recursively from that instance of left, which it has a left and data property on its node as well. This process repeats until you reach the top, in which left is null, so you print the data for the first time. Once it reaches the topmost element, it then has to go back down the call stack, to call the System.out.print.ln() method for the data for each predecessor. Then you work the right side in a similar manner with recursion and the call stack.
It's the order of the call stack. Remember 10 is the root node and still hasn't "resolved" just because we've traversed down the left side. The stack will resolve in reverse order.
I have a doubt here on insert. I didn't understand how the first node will get inserted, i didn't see any check in code whether data is null if it is first element. Correct me if I didn't understand well
Anyone know if binary trees usually use recursive for their functionalities? Still learning about data structures / algorithms, but doesn't it add up in stack calls depending on the size?
There seems to be some confusion here. If by subclass, you mean the constructor, that's not what line 9 is accessing. It's accessing the data variable on line 3. In this case, the data variable has class wide scope, allowing it to be accessed within the class. Look up the "understanding class members" tutorial on from oracle for Java, as well as variable scope. And constructors are not the same thing as a subclass. A subclass is simply a class that inherits from another class. This could have also confused you, as the data class variable has the same name as the data passed into the constructor. "This(dot)data" is the class wide variable, and data is the variable passed into the constructor when creating an instance of the class. There are quite a few things I didn't mention, as it would be too long, but I'm sure you can look it up. Happy coding!
@@trenvert123 Thank you very much for your thorough explanation! After looking at it again, I see where my confusion was. I see that int data on line 3 is a global variable that can be accessed anywhere within the Node class. At the time I was relatively new to the Trees data structure. I'm still learning though. Once again, thank you so much!
I hope you can post a video on how to build a relatively balanced tree. With the example on this video, all the weight goes to the right side of tree. Like you said in the video is not very efficient.
She always have to bash that she is the author of Cracking the Coding Interview. I know it woman. I have watched tons of your videos. Edit: I love your videos
Yep. There isn't an agreed definition of how a Binary Tree should handle duplicates. Put it in the left, put it in the right, ignore or maintain a counter of duplicates in the node
For iterative depth first search, use a stack: (Ruby code below) def depth_first_iterative(node) stack = Stack.new(node) while !stack.is_empty? node = stack.pop puts node.value stack.push(node.right_child) if node.right_child stack.push(node.left_child) if node.left_child end end
Finally someone who explains a concept without unnecessarily complicating it thank you
daaaaaaaaaaaaaaaaa!
Log sum * COS
simp XX
∪
2020 but, this playlist saving lives
It was made only 4 years ago...
Tree saves lives
Indian Lives Matter
2021
@@SlavaCh all lives matters
She just goes through the recursion in a very light way with good animation tool. Loved it. Thanks!
Gayle is a living legend ! Makes data structures and algorithm a doddle. Thanks Gayle. 😘
This was the best Tree DS explanation I have watched. She’s amazing!
Your data structures videos are so helpful! You’re really good at explaining them quickly
Very well explained code. Trees always give me problems when asked in tests.
Lol
in 2021 and this is still the most simple and well explained version. Thanks Gayle
saved me thousands of hours to understand this
thank you sooo much
very professional explanation
I've created a JavaFX App that animates a Binary Tree from an array and this video solved most of my problems. Thank you so much!
This video was so beautifully explained, it's no wonder my lecturer recommended it. Thank you very much for your video.
Recursion is such a powerful tool!
It is until ..... stack overflow
be careful tho. A lot of people overuse recursion because they wanna be fancy. But remember, recursion builds a stack in memory and does not release it until it works it's way back to the first call. This could lead to some issues. Most things that people use recursion for can be easily done with a simple loop.
only when you have few data otherwise you'll have to use alternatives like dynamic programming
and such a exhausting struggle for the stack
@@shellgecko dafuq are you talking dynamic programming for stack?
Jeez what more could you ask for. Clear, concise, and straight to the point
I would have expected the insert and contains functions to be in a Tree class of some sort, and the node to be an internal implementation operating on a comparable interface. So we can return just the data not the node itself.
I know it's outside of the scope of this video, but wondering if it's a common practice to put this logic inside of the node class.
Best run down of trees I've seen. Code with examples after is very effective.
Never knew HackerRank had a youtube channel, the explanations are so good. Thank you for making these!!!
At least you found out 8 months ago, I just found out now
@@Wiseman_RSA Atleast u found out 3 years ago..
Very well explained. I found how you visually grouped the "paths" of recursive calls helpful to understand what was happening when "traversing" the tree.
Thank you, finally someone who doesn't take an hour to explain a 5 minute topic
She is literally amazing !
One such algorithm (2:40 of clip) is the AVL Search Tree, where it prevents the skewed linked list Big O performance issue.
9:26 - What should be Post Order traversal [8, 5, 15, 10] or [5, 8, 15, 10] ?
Got it should be [8, 5, 15, 10] got a minor typo in my implementation hence was getting the wrong result.
Mind-blowing yet extremely simple recursive implementation!
she is so talented! Learned this right away thanks to her
3 years later and this playlist still getting people jobs😎
which playlist?
2 Questions: method printInOrder() what is System.out.printIn(data) doing? Also in this in-order example.. why after 5 is the next “in-order” number 8? Shouldn’t it be 10?
I understand recursively we’re traversing to the Left most depth node in the binary tree ( up until left == null ) - but I’m confused how we’re printing from that point forward.
Similar question here. Once it's on the bottom of the left side of the tree, on either left or right node, how does it jump back up to root node?
Really crisp , clear and easy explanation. DS became so easy to grasp the way you explained.
For the insertion. You have to Check if there’s a root node first of, I think. If data == null, then value = data;
it is called as,
public static void main(String[] args) {
//Say you have a tree with root node being "root"
int value = 6;
if(root!=null) {
root.insert(value);
}
}
In the insert method, what if the tree is empty, how it would insert the first node, since the code says left or right
Thanks for the video. But IMO there is an issue with how the code is written since these methods are operations on the tree data structure, not the node data structure, hence they should be located inside the respective ADT. Apart from that, the code looks great and is easy to understand. Great work!
That's what I thought too. It really confused me in the beginning till I realized it's not really a code for a node but for a binary search tree.
@kicksomeup6998 you mean that each individual node does not contain a node data instance variable? Or that the contains() method is not written as an instance non static method within the node class?
In the insert method it would not be val = data
Wow, this was precise, easy to follow and I feel I understood what is going on
Really great stuff!
I think you should have implemented contains method in the Binary Tree class instead of the Node class
This is gold!! Everything made sense now!
I love the presentation of code alongside diagrams as im a visual learner, really appreciate it.
this is AMAZING!! Well explained!
Very excellent explanation, clearest one I’ve ever heard. Deleting needs its own video, so I understand why you decided not to include it. On programming tests, I’m always like “can I not write out all the recursion methods? I hate writing all the if statements... we both know what we are talking about, this is a binary search tree ok?” haha.
I watched this video and programmed binary tree in python totally it took me 30 mins... Professor could not explain in whole semester: D
0:40 Binary Search Tree
3:08 Types of traversal
Finally, someone who write 5 the same way I do!
looks like an "s" ffs
There are dozens of us!
Are use the same technique to schedule my priorities and tasks throughout the day.
This was a really clear explanation. Thank you!
Did she just pull a recursion and I understood it? Damn she's great!
Great explanation. My only question is how to implement it such that the node can contain an arbitrary (but homogeneous) data type?
Good stuff! Makes me feel dumb when the teacher says "Let's implement this. It's really simple."
short and on point that's wat I wanted.saved my time! thanks.
2:46 Candidate: these algorithms can be very complicated, so we are not going into details here.
Interviewer: Understandable, have a good day.
There must be an implementation of delete function in this video, it will add more value to it.
Thank you for this vivid walkthrough of the code. This is one of the best of this kind
Really Great Video and Explanations within short minutes which we can understand the concept. Kudos!! Team.
Wow! Thank you so much for explaining this, I get it now. Now I just have to practice it.
This was such an easy to understand video. Does anyone know if Gayle Laakmann McDowell has her own channel?
I was confused as to how 10 gets printed before 5,8.
But it's more like, if root has something then do printInOrder of left & 'AFTER' left.printInOrder (which is recursive in itself). print the node itself. So basically the ENTIRE tree on the left of every node gets printed first...Then the root of every subtree, then then the right and finally the ENTIRE subtree of the right
Thank you very madam. you have explained the Basics of tree traversal very nicely in a simple way..
Thank you so much for the explanation!
WOW.... she explained it very well. Once you understand it... it's basically like elementary.
I think this is cleaner... but is it better/worse? (Its C++, if any wonder)
bool contains(int value){
if(this == nullptr)
return false;
else if(value == data)
return true;
else if(valuecontains(value);
else if(value>data)
return right->contains(value);
return false;
}
Is the insert() method inside Node class ?
yes
Another way would be to create a Node class as an inner class of Tree class and provide insert, delete, traversal methods within Tree class instead of Node class. I found this approach better from OO Design perspective but slightly more complex and difficult to present during a coding interview.
I recently got an assignment of a BST with satellite information on each node. I haven't found anywhere any information about this. Would you please do one about this. I am taking an algorithms class.
Its a very nice and simple way to do all that stuff , but what about the destructor? How would you do it ?
Very informative and straight-forward video, thank you!
More than amazing. Such a simple explanation. Well taught. Thanks HackerRank...
Honestly, after watching this video I got confused. I am sure that this code works fine, but why is there no Binary Tree structure being created? All the functions which ideally should be written for a BST data structure are written for a node. So if I wanted to construct a BST, do I create a Node object??
You made it very easy to understand. How simple it is and I always fear with the name trees.
Very nice little lecture, but I cannot figure it out which would be an example of a good real developer scenario in which a tree would be the more efficient way.
is the contain(value) basically functionception ?
I followed her steps on the printInOrder() method up until the 8, but then when she said 10 prints next, and then 15, she really lost me, I just don't see how it worked with the recursion. Can anyone help break it down into steps?
So basically, what you are doing here is looking if left exists, because presumably when it doesn't, you are at the top most element, which in this case, will be the smallest. If you write out the code and step through in a debugger, we use the last inserted left. When we see that this left isn't null, we call the function recursively from that instance of left, which it has a left and data property on its node as well. This process repeats until you reach the top, in which left is null, so you print the data for the first time. Once it reaches the topmost element, it then has to go back down the call stack, to call the System.out.print.ln() method for the data for each predecessor. Then you work the right side in a similar manner with recursion and the call stack.
It's the order of the call stack. Remember 10 is the root node and still hasn't "resolved" just because we've traversed down the left side. The stack will resolve in reverse order.
i understand your teachings better than my prof. nice video!💜
I have a doubt here on insert. I didn't understand how the first node will get inserted, i didn't see any check in code whether data is null if it is first element. Correct me if I didn't understand well
How come there was no class bst? Dont we want to keep a reference to the root? Also missing deletion function.
I love your videos so much, keep it up, you are one of the best
what if the inset value is same as the root? make an assumption that we go left in this case?
Anyone know if binary trees usually use recursive for their functionalities? Still learning about data structures / algorithms, but doesn't it add up in stack calls depending on the size?
you can use both recursive and iterative
is this pseudocode? Because this seems wrong. For example, how does line 9 access data in the Node subclass?
There seems to be some confusion here. If by subclass, you mean the constructor, that's not what line 9 is accessing. It's accessing the data variable on line 3. In this case, the data variable has class wide scope, allowing it to be accessed within the class. Look up the "understanding class members" tutorial on from oracle for Java, as well as variable scope. And constructors are not the same thing as a subclass. A subclass is simply a class that inherits from another class.
This could have also confused you, as the data class variable has the same name as the data passed into the constructor. "This(dot)data" is the class wide variable, and data is the variable passed into the constructor when creating an instance of the class. There are quite a few things I didn't mention, as it would be too long, but I'm sure you can look it up. Happy coding!
@@trenvert123 Thank you very much for your thorough explanation! After looking at it again, I see where my confusion was. I see that int data on line 3 is a global variable that can be accessed anywhere within the Node class. At the time I was relatively new to the Trees data structure. I'm still learning though. Once again, thank you so much!
Very clear explanation and simple understandable code, Thanks a lot
Can you give examples of a PreOrder and PostOrder Traversal? Even tho I prefer InOrder
What is the significance of the contains function in the above program??
I hope you can post a video on how to build a relatively balanced tree. With the example on this video, all the weight goes to the right side of tree. Like you said in the video is not very efficient.
it's really helpful you are like saving lives appreciate it. thanks ma'am.
She explained this 100x better than my professor could
Are these trees how people do those path finding algorithms?
Wow. The way you explained it, beautiful!
Such an amazing explanation!!! Thanks for your video
What ways are there to turn more complex trees into binary trees?
She always have to bash that she is the author of Cracking the Coding Interview. I know it woman. I have watched tons of your videos.
Edit: I love your videos
It is the first time I watch her, so I didn’t know that...
Excellent explanation !! I can tell you, you have done excellent work, simple clear, and concise well done !! and thank you !!
```
public void insert(int value) {
if(value 10``` after that? (I'll got duplicate of 10?)
Yep. There isn't an agreed definition of how a Binary Tree should handle duplicates. Put it in the left, put it in the right, ignore or maintain a counter of duplicates in the node
wow this was pretty simple explanation and easy to understan thanks
so binary trees are like the chemical equations? How to balanced them and that?
"lets add a constructor to make our lives easier" god this developer life
if only the constructor initialised the left and right to null
itsajin why? Node is a reference type....it’ll be implicitly null....
When it has 5 and it takes 5-1=4 and again calls the function, then does the previous value 5 is stored in memory till it reaches 1?
What about balancing the tree?
Ohh my God what a simple expression u are Wonderfull teacher
Amazing explanation!! Can you make more videos on data structures covering all topics plz
Fantastic breakdown. You are the truth.
You are phenomenal... Loved your video.💕💕
How to do it witout recursion?
In a large tree it can lead to stack overflow...
For iterative depth first search, use a stack: (Ruby code below)
def depth_first_iterative(node)
stack = Stack.new(node)
while !stack.is_empty?
node = stack.pop
puts node.value
stack.push(node.right_child) if node.right_child
stack.push(node.left_child) if node.left_child
end
end
is it my idea or 8 should be printed before the 5?
Just what I needed right now.
omg trees are this simple? fantastic explanation that too in this much short time.
this was so well explained and clear! thank you!