Coding Challenge #65.1: Binary Search Tree
ฝัง
- เผยแพร่เมื่อ 15 มิ.ย. 2024
- This multi-part coding challenge is part of the first week of my course: "Intelligence and Learning." Here I attempt to implement a classic data structure: The Binary Search Tree. Code: thecodingtrain.com/challenges...
p5.js Web Editor Sketches:
🕹️ Binary Search Tree: editor.p5js.org/codingtrain/s...
🕹️ Visualizing a Binary Tree: editor.p5js.org/codingtrain/s...
Other Parts of this Challenge:
📺 Visualizing a Binary Tree: • Coding Challenge #65.2...
🎥 Previous video: • Coding Challenge #64.1...
🎥 Next video: • Coding Challenge #66: ...
🎥 All videos: • Coding Challenges
References:
📕 Intelligence and Learning (Spring 2017): github.com/shiffman/NOC-S17-2...
📘 Grokking Algorithms book: amzn.to/2mMCK7Z
🔴 Live Stream Archive #87.3: • Coding Train Live 87: ...
Related Coding Challenges:
🚂 #68 Breadth-First Search: • Coding Challenge #68: ...
🚂 #98 Quadtree: • Coding Challenge #98.1...
Timestamps:
0:00 Introducing today's topic: Binary Trees
1:18 Why would you use a binary tree?
3:36 What is a data structure?
4:47 Nodes with children
8:27 Algorithm for how the tree is sorted
11:36 Node object
12:17 Tree object
12:39 Use prototype to add an addNode function
18:58 Use recursion to add nodes
20:42 Deal with the case when two values are equal
22:50 How do you traverse the tree?
25:00 What does it mean to visit a node?
27:39 Add random values
28:58 Add a function to search the tree
37:57 Conclusion and suggested variations
Editing by Mathieu Blanchette
Animations by Jason Heglund
Music from Epidemic Sound
🚂 Website: thecodingtrain.com/
👾 Share Your Creation! thecodingtrain.com/guides/pas...
🚩 Suggest Topics: github.com/CodingTrain/Sugges...
💡 GitHub: github.com/CodingTrain
💬 Discord: thecodingtrain.com/discord
💖 Membership: th-cam.com/users/thecodingtrainjoin
🛒 Store: standard.tv/codingtrain
🖋️ Twitter: / thecodingtrain
📸 Instagram: / the.coding.train
🎥 Coding Challenges: • Coding Challenges
🎥 Intro to Programming: • Start learning here!
🔗 p5.js: p5js.org
🔗 p5.js Web Editor: editor.p5js.org/
🔗 Processing: processing.org
📄 Code of Conduct: github.com/CodingTrain/Code-o...
This description was auto-generated. If you see a problem, please open an issue: github.com/CodingTrain/thecod...
#binarysearchtree #datastructure #intelligenceandlearning #javascript #p5js
Your not editing out the parts where you get confused (like with the returns in the recursive methods ) is wholesome . It’s what others don’t do . And this is a priceless lesson for everyone who has not been confronted with those kinds of problems before .
Fan since started to code.
Dan, I think you left out the most important (and hardest) part of binary trees; namely, keeping the tree balanced. Consider, for example building a tree using the numbers from 1 to 100 in ascending order. The root node would be 1, and there would be 100 nodes none of which would have a left node. Nothing but a linked list. Balancing the tree after each insert avoids this.
I wouldn't expect you to actually do tree balancing in a quick coding challenge, but I think the task should be mentioned, and should perhaps challenge us, the viewers, to work out how to do it. Or.. make it a coding challenge by itself (?)
AVL Tree
BST isn't balanced, AVL is
Upvote because I agree, but this is the first I’d learned that a BST can be unbalanced (according to Wikipedia). Not nearly as useful without it.
It's not a AVL tree! Just a binary tree!
Code for balace is ez (8 Lines), problem is run time
I love the reasoning and unedited display of bloopers. This gives it a human touch and is way more realistic, than pretending to get everything correct the first time. Thanks! 🙏🏻 😊
The pictures you saw in the image search are perfectly fine: they're pictures of binary trees; that is, trees where each node has up to two children. However, not all binary trees are binary SEARCH trees, which are ordered the way you expect. Had you searched for that instead you'd have gotten the expected results :)
I hopped on the coding train about two weeks ago and I have been binge watching all of your videos man. You are a great, enthusiastic teacher. I looked you up and saw the Swarm project and was amazed. Thanks for teaching all of us!
ur just amazing dan,,not just a perfect instructor but also a cheerful , kind human being
Do a series on data strucrures and algorithms
please?
please i beg you shiffman
PLease!
AMEN TO THAT
It'd be too late, but hell I'd get use of next semester
I love data structures and algorithms; they are so clever ideas and concepts. Love it!
that look of enthusiasm in your eyes at 0:07 is absolutely amazing :D
the recursion in visit() is dope. Only presentation on binary tree search that I've been able to listen to so far. Keep it up man
Finally, I properly understand the concept of Tree from this video. I always appreciate your teaching and your attitude. You're so much helpful. Thanks for you from my heart!
Thanks for the series on binary trees. We used them to sort images according to similarity. Thanks also for opening object oriented programming for me. 20 years of people telling me it was like dogs and cars didn't do the job. Seeing someone do practical examples made it so clear!
I just love your enthusiasm and happiness. You are one of a few TH-camrs that actually make me giggle, even though you're not trying to be hilarious. Keep being awesome! Oh and you kind of made me come back to programming. I'm an electrical engineering student myself, but I used to code a lot when I was a kid and all the way through high school, but got burned out. So thanks for making a difference in my life! (:
Thank you!
THANK YOU! You would be the perfect teacher for data structures and algorithms, please do more
Congratulation Mr. Shifman: you've made it! I finally get it about binary trees logic and why it's so useful in sorted algorythm...
I like the fact that I have tried to look for the bug with you,
but I could not see what's wrong.
I love this man .
Thks!
Thank you! Excellent! Looking forward to part 2. Thanks again. You teach/explain really well. Can you please do a complete series on data structures and algorithms?
To clarify, a Binary SEARCH Tree is what he is implementing.
A Binary Tree in general is just a tree in which all parents have (at most) two children.
The difference is that a Binary Search Tree is a special kind of Binary Tree in which the the children will either be to the left of the parent or the right depending on if the child is less than or greater than it's parent. :)
I came to the comments for this. I also believe a binary tree is usually built to remain as closely to balanced as possible.
All children should be greater than their parents.
@@robtvogel Same in my case, I was also expecting someone should have pointed this out :D
This really helps with understanding recurssion more indepth, atleast for me xD. This is awesome. Thank you Mr. Shiffman for this video.
Hey Dan, I love your coding tutorials and coding challenges they actually teach a lot. But I believe you left a really important thing outside this binary trees and thats Balancing the trees.
Great point!
It's important when implementing pathfinding for games. Find the shortest path to a certain point, for example. great explanation! thanks!
Never understood binary trees until now! This was great!!! Thank you!
Your videos are educational and joyful. Thank you for the lectures.
This what I need!
I have code that uses A* to solve 8-puzzle. It uses java's built in priority queue to hold node successors and a comparator to keep them sorted. I want to try and write something like that on my own and this seems like a great way to do it!
Duuuuuuuuude u are amazing!!!! Love your work first time ive seeen any of your videos and incan already tell ur an amazing teacher!!
Inspired by the phone book example.
In psychiatric hospital a doctor gave a phone book to a patient. After a week the doctor meets the patient again and asks him about the book.
The patient answered, the story is not really interesting, but the number of characters is really impressive.
Great job Dan love your work. Greetings from Geneva Switzerland.
@The Coding Tree
Referencing 21:26, the console.log shows the state of the object when the object is expanded in the console, not the state of the object when it is logged to the console. You need to do something like serialize the object to a string and console.log() the string to get the state of the object at the time the object is logged. I usually use JSON.stringify().
Always cool to learn from a good teacher AND from his mistakes^^
I like how the BST you randomly made just happened to be balanced. That is, there is no node such that |depth right - depth left| > 1
You're like the Bob Villa of programming and I love it
I had to a CS assignment that does math with a binary tree, with number leaves and operator inner nodes. By the way, you don’t need a tree type. When you add a node, if the root is null, you set it to the node, otherwise you recurse to the left or to the right.
I'm learning C, and this is in JS which I don't know at all. But I understand clearly what he is doing. Also from his videos I started to understand what is OOP!
Aliens from the future tell you ES2015 introduced classes in JS.
I really like the fact that you delegated the Node class to visit() and search() as this seems way more reasonable than putting a bunch of code within Tree class, because in the end Tree is just a wrapper while Node is a meaningful representation of a tree. As weird as it may sound.
A little late to the party but thank you for making this video, it helped a lot more than these academic books hah. Into my second year and just started algorithms and data structures, very interesting but mind numbing at times 😊. This video was fun to watch and helped me understand binary search trees. Thank you!
Decissions are binary. You can allways resume them as "should i do this or not". Both have consecuencies AND lead to More binary decissiones.
I've used a variation on binary trees for collision handling. They have their uses :).
In early August I finished an ~1.5yr long project for a rough visualization of several thousand particles colliding in real time. It used compute shaders on my graphics card and handled large-scale collisions in O(log(n)) time through a variation of a binary tree called a "bounding volume hierarchy". It was rather cool (after I managed to dig through the academic papers with the algorithms).
Wow this channel is amazing, just discovered it
Welcome!
A series or a video on coding a simple Gerrymandering Algorithm would be amazing!
The traversal method he is using is the "In order" transversal, which will return the numbers sorted. You can also do a "pre order", "post order", and level order. :)
The images you were looking at are " binary tree " which represents data structure tree with max 2 degree of nodes... the structure yoy wanna look for is " binary search tree "
Let's go over to the whiteboard.
Immediately leaves the shot of the white board. I can't wait to learn from this man.
Great vid as always Dan !
I love his enthusiasm
When I was watching one of your videos for the first time I thought: "Who is this crazy guy and why is he so happy all the time?" In all honesty I didn't really like you but then I watched some more of your videos and now I'm subscribed. I like to watch your videos when I'm programming because its really relaxing. Keep up the good work! Really looking forward for more videos. :)
Hah, thanks for the feedback!
@@TheCodingTrain always happy guy😅
Watching you struggle through tree algorithms is endless entertainment
you can pass as many arguments to console log as you want, it'll even put spaces between strings for you and print objects nicely
I don't know why I love this video so much :D
Really like the way you talk about programming : )
Anyone interested in a Python implementation, feel free to check out my recent lesson: th-cam.com/video/f5dU3xoE6ms/w-d-xo.html
I want to know where u buy ur adrenaline from :)))))
@@thcoura You must have a really sad life then.
It is called passion
from Alien in the future
Local crack dealer
Yeah this video really needs some editing because it seems he doesn't know what he's talking about (but he does). Overall a good explaination though.
I love this guy! Better to be entertaining and unpolished
Really awesome video. I like how you explain all these stuff
An excellent mistake at the end that brings up a very good practice: maintain reliable returns for recursive function calls. Thank you for the lesson!
This can be used for datapacking if instead of smaller or larger numbers use the commodity of the item and the more common it is the higher it is now 1 or 0 will be left or right and boom most efficient datapacking without a separate library
Great video! But Can I ask you something? In the next video, are going to only show how it works or you also explain where it used, advantages and disadvantages (like tree degradation if you add sorted sequence)?
I love learning new algorithms.
Can you do a series on data structures an algorithms?
sorry, What?!!
@@andachain Lol idk either
your name
@@Tuberex What's wrong with my name?
jk im not whoosh bait
"Insert one direction music" - i know i have the right idol. More power to you, Dan!
I love all your videos please continue
In the next video you should also add a function to remove a node! I recently had to implement my own binary search tree for a class and removing can be quite difficult in java, I would like to see if it is just as hard in JavaScript.
you make binary search looks easy thankyou so much sir!!!
Very good job dude!! I just bought that book to
Dude, I really like your bow tie!
very interesting video, love how good you explained it
Amazing! You make me wanna learn js
I had a lot of fun doing this in college using Pascal on SunOS 3.x.
you have no idea how much you help me :)
i love this man so much
omg.....some actual computer science 101 / software engineering topics ......how exciting !
Nice explanation sir, do a data structures and algorithms series, please :)
Thanks a lot brother!
you are a life saver Sir
how did you get that select bar in the google search with different programming languages?
Love you Daniel ❤️
you are AWESOME ! thank youuuuuuu!!!! :)
First of all, great video, absolutely love your enthusiam!!
I'm having issues understanding the visit()-function though, to a point where
it is driving me crazy, maybe someone can enlighten me. Here's how i
understood the code:
Taking Dans first tree with the numbers 3,5,6,7, 5 would be the root, 3 & 7 to the left
and right of 5 and 6 to the left of 7.
Now tree.traverse() is called, which itself calles the visit()-function on the root-node
with the value of 5.
visit() then checks, if a left node is present (which it is, with value 3), calls itself
again on the node with value 3 (executing this.left.visit()) and checks, whether THIS node
has another node present to the left, which is NOT the case, so it skips the first if-statement
and prints the value 3.
Following the code, the second if-statement is skipped, because there is also no right node
(this.right != null is false).
At this point, i would assume, the visit()-function is at its end, how are the
following nodes visited? Somehow the code must jump to the node containing the value 5
and then to the ones with 6 and 7, to print them all in order, but i just don't get how.
Somewhere, my explanation must be horribly wrong.. Any explanation is highly appreciated.
It's a recursive call dude. it uses stack. So, when it doesn't meet any relevant condition, then it goes back to the previous node.
Sir Will you please START JS WITH UNITY because I love your teaching skill and programming skill. When Sir you will start unity there will new world appearing
Please Coding challenge: how to draw binary tree (or ternary or other subtypes), and how to draw graph! It would be amazing learn how it visually looks like graphs and trees. I love your videos (: A viewer from Cancun, Mexico.
The first time some ancient video mentions a proper explanation of phone book and phone number!
Sir,please do a series on graph problems and approach for competitive programming
I know what a phone book is! It's a book full of phones (DUH!). So when you need a new phone, just find in in the phone book! (right?)
😅
your stupid phone book is a book that contains photos of every phones you cant just pull them out!
@@Tuberex r/woooosh
I challenge you to create a star map based on real star coordinates, converting RA & DEC coordinates to screen coordinates.
Why not use a Linter to avoid all those small bugs? Anyway, thank you for your effort.
PS: you can use "comma" in console log: `console.log('Found', someObject);`
Well, as of writing this I am one day in the future. So I am well versed in the technologies that you are describing. ^.^
Can this be used with an Expert System and Rules Structure to teach the computer by giving more and more detail but instead of a Node concept it would be frames Following Marvin Minsky's Idea of Frames and Agents?
Yo Daniel try only using one return statement and just assign a variable to what you want to return and return the variable it will make your code simpler and easier to debug and update.
UP ARROW to repeat commands in the console!!
alekmoth 36:51 he knows, right? He didn't use that because the numbers are different each time.
omg I didn't even know I watched that video 11 months ago!
great class! 😎😎😍😍😍😍
you are a good man!
I keep switching back and forth between brackets, index.html, and this video. For like the third time i have hit f5 on this video to try to make it play or refresh my web page.
Bill Nye of CS vibe , I dig it
thank you so much
Please, we really need a series on Data structures and Algorithms by Shiffman
it's hilarious how he speaks to us like we're waaaay in the future
that's so easy and common that I'm 16 and I've already seen that about 5 times and I'm not even doing anything related to it..,not doing anything at all, actually, but kinda learning programming...
I love phone books and Compact Disks
I was confused about prototype, but now I have translated the binary tree search from your code to python I see it is basically a function inside a class (in python terms anyway).
I'm still new to coding in general so hopefully someone will correct me if I'm wrong.
This was a funny parody of a newbie programmer implementing their first BST. I'm surprised you didn't put it out on April 1st of that year.
Hey Daniel,
i just started programming a couple of days ago and now I'm wondering which programming language/ environment to learn first. I absolutely love the coding challenges which are mostly done in p5js which I'm feeling more comfortable with atm but I'm planning to read your book and it is all about processing. I'd like to get good with one of the languages and transitioning between them shouldn't be too hard then but which one do you recommend for starting off?
Please keep on doing what you are doing, mfg.
Oh, this is such a hard question! It really doesn't have an answer. Does one appeal to you more for one reason or another? If you care about having your stuff on the web then I would say JS, if not then maybe try Processing? I don't know!
Yes it is such a hard question, I think I may just try to learn them both at once because I can't decide :D
Hi, very cool videos it's an awesome way to learn interesting programming concepts.
On the topic of tree structures I was wondering if you could do a video on a QuadTree implementation to show spacial distribution.
I'm using QuadTrees on procedural planet generations in games and found it very challenging but interesting.
Thanks !
Please suggest or upvote here! github.com/CodingTrain/Rainbow-Topics/issues I definitely want to tackle this.
Dan, I'm curious how we can add a value that's equal to the node to the tree