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.
Very well explained. I found how you visually grouped the "paths" of recursive calls helpful to understand what was happening when "traversing" the tree.
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 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.
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.
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?
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); } }
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!
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??
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
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.
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 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 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.
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.
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
in 2021 and this is still the most simple and well explained version. Thanks Gayle
Very well explained code. Trees always give me problems when asked in tests.
Lol
saved me thousands of hours to understand this
thank you sooo much
very professional explanation
Jeez what more could you ask for. Clear, concise, and straight to the point
This video was so beautifully explained, it's no wonder my lecturer recommended it. Thank you very much for your video.
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!
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..
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?
Best run down of trees I've seen. Code with examples after is very effective.
Very well explained. I found how you visually grouped the "paths" of recursive calls helpful to understand what was happening when "traversing" the tree.
She is literally amazing !
Mind-blowing yet extremely simple recursive implementation!
Thank you, finally someone who doesn't take an hour to explain a 5 minute topic
she is so talented! Learned this right away thanks to her
Really crisp , clear and easy explanation. DS became so easy to grasp the way you explained.
Did she just pull a recursion and I understood it? Damn she's great!
This is gold!! Everything made sense now!
Wow, this was precise, easy to follow and I feel I understood what is going on
Really great stuff!
I love the presentation of code alongside diagrams as im a visual learner, really appreciate it.
3 years later and this playlist still getting people jobs😎
which playlist?
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 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.
this is AMAZING!! Well explained!
In the insert method, what if the tree is empty, how it would insert the first node, since the code says left or right
In the insert method it would not be val = data
This was a really clear explanation. Thank you!
Thank you very madam. you have explained the Basics of tree traversal very nicely in a simple way..
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.
I watched this video and programmed binary tree in python totally it took me 30 mins... Professor could not explain in whole semester: D
Really Great Video and Explanations within short minutes which we can understand the concept. Kudos!! Team.
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?
short and on point that's wat I wanted.saved my time! thanks.
Wow! Thank you so much for explaining this, I get it now. Now I just have to practice it.
Thank you for this vivid walkthrough of the code. This is one of the best of this kind
Good stuff! Makes me feel dumb when the teacher says "Let's implement this. It's really simple."
i understand your teachings better than my prof. nice video!💜
Thank you so much for the explanation!
WOW.... she explained it very well. Once you understand it... it's basically like elementary.
More than amazing. Such a simple explanation. Well taught. Thanks HackerRank...
Finally, someone who write 5 the same way I do!
looks like an "s" ffs
There are dozens of us!
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?
One such algorithm (2:40 of clip) is the AVL Search Tree, where it prevents the skewed linked list Big O performance issue.
Very informative and straight-forward video, thank you!
You made it very easy to understand. How simple it is and I always fear with the name trees.
I think you should have implemented contains method in the Binary Tree class instead of the Node class
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);
}
}
Very clear explanation and simple understandable code, Thanks a lot
I love your videos so much, keep it up, you are one of the best
Excellent explanation !! I can tell you, you have done excellent work, simple clear, and concise well done !! and thank you !!
0:40 Binary Search Tree
3:08 Types of traversal
You are phenomenal... Loved your video.💕💕
Wow. The way you explained it, beautiful!
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!
Such an amazing explanation!!! Thanks for your video
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??
wow this was pretty simple explanation and easy to understan thanks
2:46 Candidate: these algorithms can be very complicated, so we are not going into details here.
Interviewer: Understandable, have a good day.
Are use the same technique to schedule my priorities and tasks throughout the day.
it's really helpful you are like saving lives appreciate it. thanks ma'am.
This explanation makes my life simple against Binary Tree Thanks Alot !! :)
Ohh my God what a simple expression u are Wonderfull teacher
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
This was such an easy to understand video. Does anyone know if Gayle Laakmann McDowell has her own channel?
omg trees are this simple? fantastic explanation that too in this much short time.
Great explanation, thanks.
Sincerely,
Someone who smokes a lot of trees
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.
How come there was no class bst? Dont we want to keep a reference to the root? Also missing deletion function.
There must be an implementation of delete function in this video, it will add more value to it.
Fantastic breakdown. You are the truth.
You're awesome Ms. McDowell! Many thanks.
what a coding skills mam just awesome '
Well explained. Exactly what I needed. Thank you.
Gayle you is amezing!! I love you , ty for being inspiration for all women in cs area.
what if the inset value is same as the root? make an assumption that we go left in this case?
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;
}
this was so well explained and clear! thank you!
She explained this 100x better than my professor could
Great explanation. My only question is how to implement it such that the node can contain an arbitrary (but homogeneous) data type?
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 actually understood binary trees after this video! Wow.
Well explained. Works like charm !! Thanks
Just what I needed right now.
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 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.
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.
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?
You are an amazing educator! Thank you
Its a very nice and simple way to do all that stuff , but what about the destructor? How would you do it ?
Amazing explanation!! Can you make more videos on data structures covering all topics plz
Thank you for posting such a useful article!
the perfect video on trees
"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....
Idk you’re just great. Thank youuu sooooo much. Saved my life😂
so binary trees are like the chemical equations? How to balanced them and that?