Binary Search Tree - Beau teaches JavaScript

Подписаться 10 млн

Просмотров 115 тыс.

50% 1

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

Опубликовано:

25 мар 2017

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 80

@marshalltrimble383 2 года назад

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.

@user-bv3ju3zf8u Год назад

Not only a detailed code walkthrough, but also de-jargoned. Instant sub

@ermalgashimramori 7 лет назад

Thank you, loved the way you approached the subject, and it all clicked in for me. Thank you.

@bryang3044 7 лет назад

Thank You so much. Your data structure videos have made the difference for me in cs fundamentals.

@pranshul67 6 лет назад

thank you! Finally understood node insertion in BST after watching your video!!!!!!!!

@Lashistoriasdelilith 2 года назад

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.

@blue_mustang_ Год назад

High Complex topic brilliantly explained.Thank you very much !

@xerxius5446 4 года назад

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; }

@vishnuumakanthan9583 4 года назад

Thanks a Lot, man..really appreciate the effort you took.

@jugzster 7 лет назад

Clear and detailed way of explaining BST, thanks! Amused by the way you say "root" :-)

@CST1992 2 года назад

Why amused? It's the perfectly accurate pronunciation of the word.

@rowanolson5161 4 года назад

Thank you! was struggling with this.

@NumbersAndLetterz 6 лет назад

This was great! Thank you!

@ram_bam 7 лет назад

Awesome video and explanation.

@emmanuelamoako8963 3 года назад

thank you, I enjoy your teaching. You good!!

@user-ej3iw8lw3w 2 года назад

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.

@sejinmajnaric2884 3 года назад

Thanks a lot, Beau! :)

@doonssunshine3696 3 года назад

Clear Explanation

@Eslam-ig2gf Год назад

love it, thanks so much

@rajbannasa7662 2 года назад

Thank you so much sir ❤️

@adriangrozavu1632 7 лет назад

The audio quality could be better, but otherwise I'm liking it

@beqasirbiladze8831 5 лет назад

4:23 23 left child is 19 and not right

@Falzer 2 года назад

Thank you so much!

@emuraqhan5954 4 года назад

Thank you so much! :"

@yogeshsharma5168 3 года назад

Because of diagrammatically explanation it cleared all my doubts.. Thank you so much for this amazing idea of teaching 🙌

@jayp6955 7 лет назад

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.

@some5794 Год назад

can you do remove without recursion tho?

@motezart2867 6 лет назад

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.

@some5794 Год назад

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.

@timothylefkowitz3429 Год назад

THANK YOU

@Satishkumar-rx7oy 2 года назад

thanks so much

@jorgechinchilla6505 5 лет назад

thanks a lot!

@canmertinyo 10 месяцев назад

Thanks

@joris7571 4 года назад

Hi, thanks for the materials. Is there any reason for not implementing isPresent() recursively in your exemple ?

@vsueiro 4 месяца назад

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.

@thoaily8352 3 года назад

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

@charleslamb5810 2 года назад

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 =)

@moswilam91 5 лет назад

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..

@pist5343 4 года назад

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

@victorvondoom2350 2 года назад

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

@atsepa 7 лет назад

In the final example is 4 the root ?? Is the root the first value you add always??

@atsepa 7 лет назад

after rewatching .... yes the first element added will be the root

@DanielSanchez-kg8zy Год назад

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.

@MyALPHAguy 5 лет назад

What is this tree for? When am I going to use it?

@JohnSmith-tw3uq 4 года назад

Technical interviews and school. Aside from that, not much in the work place.

@jumpman23nith 4 года назад

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?

@ashianagi 3 года назад

Yup that’s correct.. You can even test it in the console,

@some5794 Год назад

can you explain in one video what would be the real life applications for it?

@constantin6021 3 года назад

`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

@patrickmwangi7918 3 года назад

What if node.value = 0; Zero also returns false and it would cause issues.

@raha5184 3 года назад

Can someone explain why are we setting the value of this.root to the return value of removeNode() ?

@ashianagi 3 года назад

I thought the same thing, I console logged it and I don’t see why we need to assign it to this.root.

@anilkumard3087 2 года назад

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..

@dusanmarsa4597 7 лет назад

Good tutorial, but where i can use it in JavaScript? What is it good for? Some reallife examples? :) Thanks

@mediaskate648 7 лет назад

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.

@DRzFlacita 7 лет назад

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.

@dusanmarsa4597 7 лет назад

So, this tree can be somehow use for strings too? How is that? It can be maybe used for Questions tree too?

@mediaskate648 7 лет назад

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.

@dusanmarsa4597 7 лет назад

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

@piperxy 7 лет назад

Yes, What Dusan Marsa said, some real life examples please?

@DRzFlacita 7 лет назад

Check my reply to Dusan. :)

@piperxy 7 лет назад

Appreciated!

@GanpatKakar 6 лет назад

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.

@lucasJRS Год назад

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).

@aminKedir 4 года назад

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.

@martinXDDK 6 лет назад

tree ? its more like roots

@mathiassalome1749 3 года назад

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??

@petrolhead8822 7 лет назад

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?.

@freecodecamp 7 лет назад

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

@petrolhead8822 7 лет назад

Great! Thanks for the info.