Coding Challenge #65.1: Binary Search Tree

Other Parts of this Challenge:

References:

Related Coding Challenges:

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

#binarysearchtree #datastructure #intelligenceandlearning #javascript #p5js

[adamoja]

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.

[kenhaley]

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

[Tordek]

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

[ali_gaming]

Do a series on data strucrures and algorithms

[ProBloggerWorld]

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! 🙏🏻 😊

[kosmic]

ur just amazing dan, , not just a perfect instructor but also a cheerful, kind human being

[kolozubix]

that look of enthusiasm in your eyes at 0:07 is absolutely amazing :D

[jorgegranada]

Decissions are binary. You can allways resume them as "should i do this or not". Both have consecuencies AND lead to More binary decissiones.

[rushishah]

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 "

[steevenpetit-homme]

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!

[yungrolex]

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!

[avatar]

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

[foolishsamurai]

I want to know where u buy ur adrenaline from

[toppercent]

I love data structures and algorithms; they are so clever ideas and concepts. Love it!

[NinjaKyou]

Can you do a series on data structures an algorithms?

[wyattelliott]

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

[Nxluda]

Let's go over to the whiteboard.

Immediately leaves the shot of the white board. I can't wait to learn from this man.

[iamamcnea]

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

[Holobrine]

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.

[FredoCorleone]

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.