Binary Search Tree - Beau teaches JavaScript
Вставка
- Опубліковано 25 бер 2017
- A binary search tree is a tree data structure with only two branches for every node. Learn how to implement a binary search tree in JavaScript ES6!
💻 Code: codepen.io/beaucarnes/pen/ryKv...
🔗 Info: en.wikipedia.org/wiki/Binary_...
🐦 Beau Carnes on Twitter: / carnesbeau
⭐JavaScript Playlists⭐
▶JavaScript Basics: • JavaScript Basics Course
▶Data Structures and Algorithms: • Data Structures and Al...
▶Design Patterns: • Design Patterns - Beau...
▶ES6: • ES6 - Beau teaches Jav...
▶Clean Code: • Clean Code - Beau teac...
-
We're busy people who learn to code, then practice by building projects for nonprofits. Learn Full-stack JavaScript, build a portfolio, and get great references with our open source community.
Join our community at freecodecamp.com
Read great tech articles at medium.freecodecamp.com
Can we all appreciate how well he went over this and well he tried to make sure that the depth of this was covered along with walking the viewer through a journey of creating a mental map and understanding of a BST.
Not only a detailed code walkthrough, but also de-jargoned. Instant sub
I had to slow down the video because you speak too fast to follow the code while you explain it. The explanation was really clear. Thanks.
Thank you, loved the way you approached the subject, and it all clicked in for me. Thank you.
Thank You so much. Your data structure videos have made the difference for me in cs fundamentals.
thank you! Finally understood node insertion in BST after watching your video!!!!!!!!
Very well explained !
Here is the shorter version of add function if anybody wants a terse code
add(data, node = this.root) {
if (this.root === null) this.root = new Node(data);
else if (node === null) return new Node(data);
else if (data === node.data) return;
else if (data < node.data) node.left = this.add(data, node.left) || node.left;
else node.right = this.add(data, node.right) || node.right;
}
Clear and detailed way of explaining BST, thanks! Amused by the way you say "root" :-)
Why amused? It's the perfectly accurate pronunciation of the word.
Thanks a Lot, man..really appreciate the effort you took.
High Complex topic brilliantly explained.Thank you very much !
This was great! Thank you!
Thank you! was struggling with this.
Awesome video and explanation.
Is there something weird with the add function on the codepen link? It doesn't seem to have a closing bracket. Maybe it's just me but bst.add(10), for example returns null.
**Not sure why, but prob seems gone now.
thank you, I enjoy your teaching. You good!!
A balanced binary tree, also referred to as a height-balanced binary tree, is defined as a binary tree in which the height of the left and right subtree of any node differ by not more than 1.
what happens is the left sub node after the right sub node is lower than the left node??? for example instead of 1 it was a 2, and instead of 4 you had a 1. Then you would be replacing 3 for one which would have two children greater than itself.
Hi, thanks for the materials. Is there any reason for not implementing isPresent() recursively in your exemple ?
It is recursive, right? It’s just using a while loop (and not calling a function) to do the recursion… It seems that every time the while loop runs, the `current` variable will be a child node, if it exists.
hi just some questions :D, why data is 23 and why in 5:25 23 it says that is null when in the graphic obviously appears?, im new in all this about nodeTrees.
Thank you so much! :"
Thanks a lot, Beau! :)
The audio quality could be better, but otherwise I'm liking it
Clear Explanation
love it, thanks so much
Thank you so much sir ❤️
In the final example is 4 the root ?? Is the root the first value you add always??
after rewatching .... yes the first element added will be the root
Thank you so much!
4:23 23 left child is 19 and not right
Cool. Another tip is to try and use while loops instead of recursion for better performance. One way to do this is to say while(node), check your cases, set the node equal to the left or right child. The while loop will terminate on null. This is done for the findMin, findMax functions but not for the add function. As an exercise, see if you can rewrite the add function using a while loop instead.
can you do remove without recursion tho?
thanks a lot!
I'm wondering if there are any built-in BST classes in JavaScript because I don't want to implement the tree every time I want to use it
Would probably be cool, but perhaps abstraction is required for something like a Bst.
Otherwise people would inevitably have complaints about the way it is implemented in Javascript natively.
Preference creates conflict.
Solution: just write it once the way you like it, then push to your github/bitbucket.
Then reuse whenever necessary =)
wat about 17 number that you were about to delete , theres no right node with left child so what should i do in such a case
Because of diagrammatically explanation it cleared all my doubts..
Thank you so much for this amazing idea of teaching 🙌
What if you want to remove a node but its right node doesn't have a left child? Which node will take the place of the node to be removed? Just wanted to confirm my guess.. It is going to be the right node?
Yup that’s correct.. You can even test it in the console,
thanks so much
What is this tree for? When am I going to use it?
Technical interviews and school. Aside from that, not much in the work place.
THANK YOU
Good tutorial, but where i can use it in JavaScript? What is it good for? Some reallife examples? :) Thanks
Any time you want to sort some sort of values and be able to locate them quickly. Because of their left and right properties searches are cut in half after each recursive call to the search effectively making the search much faster.
Real life example: Someone is trying to create a new account on a Reddit (just for an example). They have to come up with a unique username in order to create an account. They start typing in characters, and each time they do this, Reddit will let the user know if those set of characters are already taken up (invalid) or free to use (valid). How does Reddit know whether the username is taken or not? They have a sorted list (like the binary tree) that allows them to search quickly through the millions if not billions of usernames already taken. Searching an extremely large list in this way would be much faster than starting at the beginning of the list and checking every single username to see if it is already taken.
So, this tree can be somehow use for strings too? How is that? It can be maybe used for Questions tree too?
Dušan Marsa yep JS can alphabetize by doing comparisons. "AZ" > "AA" === true. You can use this to have a fast binary search for the given string value.
Ok thanks, :) help a lot. And to author, you can add some real life tips for this types of videos. It helps a lot to understand what is going on :) thx
can you explain in one video what would be the real life applications for it?
Thanks
Can someone explain why are we setting the value of this.root to the return value of removeNode() ?
I thought the same thing, I console logged it and I don’t see why we need to assign it to this.root.
Basically it's a recursive function... So once removal of a node is done it will return you complete modified tree which is pointed to root..check stack trace to see it... If you inspect root, it is nothing but the modified tree..
`if (node.left === null) { ... } else if (node.left !== null) {...}. We can remove the 2nd if statement.
I think that `if (!node.left) {...} else {...}` is more readable
What if node.value = 0; Zero also returns false and it would cause issues.
Thanks for the upload, in my opinion, I think it could have been better and more clear if you built it from scratch while explaining step by step, coz I think a lot of people got a bit overwhelmed when they saw that bunch of code the first moment of the video. but thanks again anyway..
You're right that it feels a little overwhelming, but after the first example you see its not actually very complicated. Just lots of decision-making with ifs.
I think Its better this way - you watch his explanations AND THEN you try to build YOUR OWN tree and see if it checks out with his
Yes, What Dusan Marsa said, some real life examples please?
Check my reply to Dusan. :)
Appreciated!
Thank you for providing such a valuable data structure tutorial, but i have one point about binary search data :-
1. How we can make this binary search tree as a sorted binary search tree.
Lets say i want to insert this data :-
bst.add(50);
bst.add(23);
bst.add(72);
bst.add(67);
bst.add(55);
bst.add(62);
After adding this data my data structure will look like this :-
{
data:50
left: {
data:23,
left:null,
right:null
}
right: {
data:72,
left:{
data:67,
left:{
data:55,
left:null,
right:{
data: 62,
left:null,
right:null
}
}
}
}
}
But As you can see this data structure is not correctly sorted for a sorted binary search tree.
As i came to this conclusion that, first we need to sort our inserting data then only our binary tree can be sorted.
how come that is not a sorter binary tree? All the nodes left from 50 are minor (just 23) and all at right are bigger (72, and then 67, 55 and 62 are less than 72).
is there any way to donate to this guy? i mean i pay for shitty subscriptions already, it's nice knowing your money is going to someone who deserves it for once.
The implementation example you showed just flicked on the switch! oh those wasted hours tearing my hair out, Why oh why didn't my instructors just give us a damned clear example??
tree ? its more like roots
You should provide exercises if you post only theory, it is almost useless.
Why you won't write some problems and publish it as a PDF?.
Your in luck! Most of these videos align with exercises on the beta freeCodeCamp curriculum. There are 10 interactive challenges based on Binary Search Trees. Here is the first one: beta.freecodecamp.com/en/challenges/coding-interview-data-structure-questions/find-the-minimum-and-maximum-value-in-a-binary-search-tree
Great! Thanks for the info.
wwhat if the note down there also has children?
You talk too fast.
Grades no worries. You’ll get a full refund.
You complain too much (don't take it personal, just using the same style you've used in your reply).
You just gotta study up more bro.
jesus christ.. slow down a bit. You speak like if you are in a hurry
add(data) code is horrible! Just put first if(node===null) inside searchTree() and you can remove half of "else if" EASY
great example but trash explanation