Coding Challenge #65.1: Binary Search Tree

hello welcome to a Isis coding challenge this is a coding challenge the coding challenge today right now is binary tree oh okay what's do it it's actually kind of an interesting thing so first of all what I've been reading this book recently I just finished it called grokking algorithms it's great by Adi I'll put a link to it in the spice Odyssey ah ba ba ba sorry I pronounced that wrong I'll put a link to it in the this video's description and I it's been refreshing my brain about all these algorithms that I make up once learned and then never really bother to use again even though they are vital and important and but what I really want to ask in this series because I'm gonna have a bunch more related to this sort of similar topic is what kind of creative outcomes can you have with this so I'm going to come at this from a very no no point-of-view approach let's just look at the literal binary tree algorithm let's make a version of it I'm actually not going to include any visuals I'm just going to show you the results in the console and I'm going to ask you the viewer to make some type of visual out of it or to do something more interesting with it so maybe when I get to the end I'll have some ideas for you because I don't have them right now so look I have all these pictures of binary trees behind me and let's go over here to the whiteboard and let's make a diver so why would you need a binary tree first of all and actually this is this is the example that's in this book so I'm going to borrow it pretend this was a phone book lot of fun book but it's a big book it's a book of random numbers that's another story for another time and let's say I wanted to find where I am in this book why would you even know what a phone book is such a super trend is a phone book people of the future aliens of the future a phone book is a book I'm thinking to you up there that you pull people off the future a phone book is a book with people's names in it and everybody's phone number oh my god a phone number is a nut sequence of digits that you use to call somebody on a phone a phone let's just I don't know how far into the future you are hopefully you still know what a phone is anyway so let's take this book with a list of people dictionary maybe dictionary it's a dictionary a dictionary it's a book list of words and I want to look up the word rainbow or train pick your word one way I could do is I could go to the first page thank you sorry Apple and I could look at every single word on the first page it's not there and I could look at every single word of the next page it's not there they go get everything aware of the next day she's not there but I know rainbows are which is going to be you know somewhere around in 2/3 so I have a sense of where it is but another way I could look if I could just go straight to the middle and I could say ah is is the words that I'm seeing here now does it come before or after rainbow in the alphabet if it becomes before you can but because before then I'm going to go half way towards the end then I can go half way back then I could go half again like it keeps finding like dividing all the words up in half did I play this with my kids all the time let's guess a number between 0 mm and I always guess 500 and they say well it's too small so I'll guess 750 well that's too big so I'll guess you know what everything between those two 625 I don't know that so 6 tango oh my god I can't do the math so so that the point is a binary tree is a data structure that allows you to move through sorted data by dividing it in half now there's a lot more to the efficiency of the of house of the binary tree beyond that but let's just start by designing one and come back to some of these questions later so first of all what do I mean by data structure here's a data structure bar x equals 10 a data structure is a single number here's another data structure far num equals to 10 10 11 12 this is an array it's a list of information there are up I can have an object in JavaScript which is a mapping of keys and values um you know favorite color whatever purple so these are different kinds of data structures that are familiar with that's a structure where you store data and we could get fancy about if there's things like lit linked lists which each objects each thing points the next day so you can only get to it from the beginning by going through all of them and boy I should make some other videos about all these things there's stacks and queues and all this stuff a binary tree is a data structure that works like this there is a this idea of a node this is a node and I'm going to call this node the root of the tree and it and it has maybe a child - children - children nodes one the left one and one the right one is a binary tree because each node can only have two connections to children other kinds of trees can have all sorts of variable and house here here it looks like this now this is the way that data is organized but I said the data is sorted what do you mean spot that doesn't look very sorted I mean I could imagine this being sorted well strangely enough it's it's it's sorted into quite a remarkable way and the way that you build a tree is by adding notes to it one at a time so let's use let's use numbers somebody shout out a number there's nobody nobody around like to get anybody to use number oh well obvious one I there's a chat going on but I can't see that far for me so let's say I have the number 10 I'm going to add these numbers 10 5 15 7 to 9 31 this is a list of number so I just sort of thought in my head bit of an ADD so I'm going to add to the tree first 10 so 10 the tree is empty so the root node gets the number 10 now I want to add 5 into this tree and right now the root node has 2 empty spots as soon as I make a note it gets two empty spots now five is coming in here and I believe if 5 is less than it should go to the left and if it's greater than it should go to the right I hope I'm doing this correctly there's you know I think it'd work either way but there's a standard so 5 is less than 10 so it's going to go here and now this has a left and right with 915 13 is more than 10 it's going to go over here and this has a left and a right 7 7 is less than 10 so it goes over here up 5 it's greater than 5 so it goes over here and now this has a left and right 2 2 is less than 10 2 is less than 5 2 goes over here I'm Finnick I can't keep track of the way that I'm using dotted lines they're not so this okay because we got to get through the whole thing 9 9 is less than 10 it's greater than 5 scream 7 9 goes down here 31 31 is greater than 10 31 is greater than 15 so 31 goes here so actually I'm going to sort of erase these these are all the empty spots so this is the tree so how is this sorted let me tell you something this is most certainly sorted it's sorted because if I go all the way to the left watch this let's go to the left 5 let's go to the left - lets go to left oh nothing left let's point out 2 now let's go back ok fine oh now let's try oh I'm sorry go to the left go back now we try to go to the right sorry go to the right nope so let's come back go up here 5 now if we go to the right yes 7 go to the right 9 actually sorry 7 we should try to go to the left but we weren't able to go to the left so we came back 7 and now we go to the old this is so hard let me do this again I don't know if I should edit this we come back but the algorithm of how we traverse this tree is we want to visit every node visit a node and when we do that we want to go to the left which means that means visit the nodes of the left so we're going to implement a worker algorithm a recursive function a function of references itself visit the node go to visits up and so I should say start with the root and then visit left so we keep visiting less all the way as far as we can eventually we can't visit left anymore so then we might say you know a print I'm just going to say print the value so we come up and print the value to what's the next thing we do is we visit the right so now we go down here up there's nothing there so we come up here and then these are finishing where are we here now we we finished visiting five so now we print out the value 5 and then we visit right seven what do we do when we visit seven we then go to the left nothing there so we come back and print out seven then we visit the right so we go to the left nothing there print out nine go to the right nothing there back back back here then we print out 10 then we go to the right and we try to go left nothing there 15 then we go to the right nothing there nothing there 31 and we're done so this tree magically the way that the things are added to the tree end up into sorted order because what we're doing is we're basically saying I want to look here's your ties back to that phone book example oh my goodness can't believe I miss it if I want to find the number nine right let me find the number nine somewhere I'm going to find this name in the FOMA because the number nine might be associated with some actual important piece of information we need the nine just being like a key I can say is nine less than or greater than ten and if this tree is balanced nicely meaning there's the same numbers on the left and the right I now have eliminated I don't have to search through half of the data whereas if I have an array and then need to try to find look through the array to find something in unordered in an unordered array I have to check every single option so this is the structure how do we program this this is the next step okay so back over here we can see all of these nights visualizations of trees maybe I'll try to add a little visual something just so you can get how do you get started with visualizing it but but hopefully that gives you an idea of what it could be useful for talk about that okay so now let's start to program this so what do I need how how would I even get started programming this well think about it I think I definitely got to need a node object so I'm going to write a constructor function called node and it's going to have a left and a right I'm going to set those equal to null just to sort of explicitly say when I make a node and the node should have some kind of value or label I guess I'll just use numbers maybe I should use text I don't know what's better but let's call it a label so I'm going to make it's like the sort of data at that node I'll call it value right so when you make a node it has a value and it has a left and a right which have no nothing connected so far let's make I think let's make a tree object - I don't know if the tree is really going to need anything but a tree is going to have a root node and then also so that when the tree starts this dot root equals null so the only thing one of the things that's interesting about this data structure is I only ever need a reference to the root if I have a reference to the root by moving throughout the tree I can find any element okay so what happens if two numbers are equal well we'll get to that that's a great question okay so what I want to do I need a function I'm going to use prototype to attach functions so I want the tree object to have a function called add a node and it gets a node as the argument and the first thing I'll do is just say if this dot root is is equal to null then this dot root equals n great so then let's say node n equals a new node well let's use numbers for right now because I think that'll be a little easier to see five and let's let's make a global variable just tree tree is your project called binary tree but tree equals a new tree and I have this node and tree add node and okay so and then let me just say console dot log tree so let's see so this should be so by the way I'm using p5 here but there's actually nothing about this that I've use it there's nothing here that I using p5 other than the setup function I have no canvas in there so it doesn't draw a canvas but I'm actually going going to probably out and I have an error or someone just pointed out if this dot root equals no if I want to test if it's not I need a double equals and if I really really really want to test but could use a triple equals some guy just want to make a video only about double equals which is triple equal such a funny little concept maybe I should do that Frehley today okay so there we go so now let's just take let's run this program where am I here oh I have an error Matt error sketch dot yes line one oh my goodness I'm in programming in too much Java today this should be bar three right I don't need to give it a type and good this would be Bar n boy I programming a job out earlier today you can tell right okay whoops wrong thing console dot log not capital tree trees that particular object there we go so we can see the tree has a root and has a node the root is a node with a left and right being null perfect okay here we go so we're in pretty good shape now what happens if I create another note and you know what you're I don't really need this variable here I can just do this I don't need a separate barrel I can just add a new node I could also if I really wanted to what if I just just to make things a little simpler under stay add a value five and I'm going to have this function create a node from it and so this is really the same sort of thing but this is just a little simpler now because I can have that function take care of that okay so what happens now if I say add value three now first of all when I write that things that are less then go to the left let's go back to the browser that binary tree yeah looks like these examples oh whoa I don't know what this is oh boy I don't know what these what's going on with these binary trees what yeah this looks right so less than goes to the left some of these images are doing so exploit Li different source is doing not to not rely on Google Image Search okay let's go back to my code so let's say I want to add node okay so I have another error this needs to be add I change this to add value you guys should just call it add but whatever so now what do I do if root is no it should be the root of that node so what grew does not know hmm so what I need to do is say this dot root add values really what I should do this is interesting this dot root add value okay listen to this this is crazy so I actually I'm losing my mind here ah okay otherwise here's what I want to do otherwise I got it this dot root add add node sorry dot add node and so okay what am I doing here so what I'm doing is I want to say if the route is empty tell to just set it equal but what is this function this top root add note this means I need a function as part of this node that knows how to add something to itself oh this is great alright so I need a no function no dot prototype dot add node equals function no n so that's the node that's coming in now what happens if I'm a node and this comes in well I want to compare the value of n if n value is less than my value if n value is less than my value then this dot Left equals that node right it should be so if I'm adding it to myself if it's less it should go there otherwise this dot right equals end but this isn't correct this is a nice idea right and it will work for just the root because when these two things are empty it will get added here but what if it goes to add to the left but there's something already there what needs to check against that one I mean that one it should then go to the left or entry check it get that one there may be that it should go to the right so here's where I need recursion what I actually want to do is say this dot left add node N or this dot right add node n right because I want to just say keep going but what if this not less is it is no so if this there's probably more elegant way to write this if this got left is null then it should be that value otherwise keep going same thing here if uh-oh if this stock I'm sure I see a lot of chat messages telling me I'm doing something wrong so I'm sure I'll discover that in a second if this cut right equals null this dot right this dot right equals n elf and note line 17 o VAR n okay okay big deal that was all it was that was all was because I keep writing notes okay so I don't think I have anything hope late on anything majorly wrong I'm sure there is I'm sure there's a way we could write this like a restock sure this to be a little nicer but it is saying exactly is doing right if this value should go to the left if the left is empty perfect put it there otherwise recursively go and call that function again otherwise if otherwise if it's go to the right now here's the thing if it's equal I kind of want to do nothing right now so I think what I'm going to do with equal if the note is equal it just shouldn't go anywhere and so in that case I can say if else if this dot else if n value is is greater than this value so actually in the case of both two values being equal nothing will happen so an equal value will get added to the tree okay so let's take a look at this okay let's run this what am i let's run this so the tree has a root which has a value of five and to the left of it has the value of three boy this is a really awkward way to look at it so we're definitely going to want to visualize this in some way to see if what we're doing makes sense but we can see that this is correct now if I were to then say add the value it's weird that I console logged it later it was there add the value 7 let's try that the tree has a root and the root has by zoom into this elected the roots value is 5 the left value is 3 and the right value is 7 that's exactly right let's just try one more thing let's just I don't know let's add six that's a little bit tricky right but it should be six should go to the right of five to the left of 7 so let me refresh this again the tree has a value note the root of the value of five left is whoops on the value of three sorry right has a value of 7 and to the left of that is the value of six so this is no way to understand or see this is like I'm kind of used to this weird JavaScript console but the tree is there right only thing I need to know is the root so remember remember how I said okay well what if I want to then look at all of the values or what if I want to search for a minutes building which is like a binary search tree the ideas or storing all this information in this tree I could search for something in it so how do I traverse the tree how do I traverse the tree so let's just look at how we would traverse the entire tree and this is exactly it - I want to start by visiting the root and when I visit the root I visit the left then I print out its value but and visit the right but that's then recursively so visiting the left means is if this left exists it left until there's no left then come back then print out the value then visit the right center so this algorithm we worked out very hard to hold this into your head so recursion is new to you I think I have a video where I go over it look at like factorials like math I'll make drawing some like recursive trees and fractal patterns you might look for some of those videos but this is a tricky thing to get on so let's create a function now that's part of the tree prototype I'll call it traversed and it is a function that says root dot root visit wait that's right so what I want to do is first visit the root node okay and then and the note you know what I need to do now I need to make some separate separate files triana make a file called trees and I'm going to make a file called a note no js' oh boy it's not a problem no js' so if I go to sketch I just want to be able to pull this code out and look at it on its own so tree just has v3 functions now the add value the Traverse and the tree so the tree is just really a wrapper for the root that's all it kind of does the node is where all the sort of guts of the algorithm is is is so I want to take all this node stuff and put it here in this file and here we go so now all I have is so far is the constructor to create the node which has a value and is no left and right and then this add node function which recursively figures out where that to keep going through more and more notes that were to add it now what I want to add is a function called visit and what does it mean to visit this left visit this dot right visit so always want to go to the left first because I want the lower values first so that was definitely right and then I want to visit to the right but in between if I go all the way on the left if I want to actually do something I want to process the value or check what it is here's where I would say console dot log this dot values so here's the problem is though I don't want to say this dot left up this dot left I visit if it's known so only if this dot left is not equal to no and I know I could in JavaScript I could just say as long as this dot left exists but just in case you couldn't have the value of zero which is going to cause me a problem so I'm going to I'm going to stick with checking to make sure it's null and if this stop right does not equal to null this dot right dot visit okay look at it so simple beautiful elegant I love this kind of stuff line seven I have something wrong in line seven no no dot prototype thank you I love having a chat that debug this stuff okay so here we go I think I just sort of typed this from scratch could this possibly really work so let's now let's go here and see if in the sketch I'm going to now say three dot Traverse and I should just see all the values in sorted order so okay tree is not huh tree is not defined oh of course I always do this I forgot to add a reference to these two new files I just invented a whole new JavaScript library called node that's a yes not really tree is there's a whole big server-side JavaScript programming pretty more called node so I feel like maybe a little bit weird that I called my file knows that yes but will live ok root is not defined this stuff [Music] I forgot this duck clearly did I forget it anywhere else I don't think so let's run this again there we go look at those values 3 5 6 7 ok let's try this in a crazy fun time way because because of this already been so much fun let's say for VAR I equals 0 I is less than 10 i plus plus let's add a random number between 0 and 100 and I'm going to floor it just so it's integers even though I don't really need to and I'm going to console.log tree and say tree duck so i'm stead of hard-coding the numbers I'm going to pick random one and let's run it please look sorted these looks sorted these looks sorted it's great and lets out a thousand yeah it happened pretty quickly so I mean you would have to sit out here's the thing let's let's go back to just doing this with and let's look at the actual tree the root has a node to the left which is 68 no the the root is 89 to the left is 68 to the right is 93 again this is no way to look at it so we're done with the binary tree I didn't actually add a function that is that involved searching the tree which I probably should that would kind of make sense but so we could search so we got that let's add that let's add a function that searches the tree and it's going to be very similar to traverse so we're going to say three dot prototype dot search equals function I'm going to search for a value and we're actually just going to do the exact same thing Oh sort of we're going to say this dot root dot search for Val so again the tree object is just a wrapper for the root and we're going to say search the root so now this visit function is going to be very useful because we're essentially doing the same thing but what we're first doing is we're first thing does this dot value equal Val right my first then I want to say console.log found [Music] plus Val and then otherwise otherwise if this value is less than note sorry if val is less than this value then and and this dot left is not equal to no then I want to enough then I want to go and search for that value here and then I'm going to do the same exact thing for the right and I'm going to search for the value to the right so this is how I could just say hey is the root the value no but I'm less than it so just let's look at everything to the left so I don't need to this I'm not traversing the whole tree I only don't need to go the one direction that I need to go so insert one direction music right now okay so let's see if let's do this let's see if this works so this what's in the tree right now all these numbers so if I say tree dot search 53 this dot root search is not a function what did I do wrong oh I called it I sorry I called it visit again this should be searched let's do this again so I want to say tree dot search let's look for 61 sounds 61 can you guys see this refresh this again well you can't see at the bottom there because it's cut off so let's do this ah sorry hold on so let's do a tree dot search and let's look for something it's not there so 9 is not there undefined so that's pretty good I probably should have something where I mean that's why I might want to explicitly somewhere say at the end return return undefined or return not sound but I can basically say here now in my wherever I oh you know I should just return so that's what I should do sorry run right when I found it what that's what I should do to make more sense right here I should say return a a metalic return the node return this so that's I found it at this notes I'm going to return the note and then at the end I believe if I just say return you know no so if it never finds it eventually it's going to recursively percolate through all these functions to get to the end and return I think that's right - let's do this again so now it's a tree dot search for 20 which I know is in there somewhere and I got undefined oh you know what this is not the right place for this because right because it could be eco cuz it's equal no hmm vertical both time host wait wait let me take this out for a second after think about that tree dot search for undefined what's wrong here what did I miss return this console dot log sound Wow oh whoa this should save our sound I don't know why I didn't have a sit I didn't add the part I'm really sorry everybody on my brain must have just melted I bar found equals this so if sound is not equal to no console dot log you know found and then I could I could put that object out otherwise console dot log not not found I don't know why I missed that so we're searching okay okay so now I should say tree search ten found 10 not found so why does that happen why is that oh oh oh no it can it sound it but said mascot what am i oh oh oh oh oh I might my returns is off my return is all messed up think about this boy this is hard search sounds oh no I'm in the wrong place oh I mean I'm in the wrong place this is where I need I just want haven't really think thought about what I'm doing it helps to think about what you're doing what am i doing I want the tree this is the function I'm calling I want this function to return something it's printing out the right thing the whole point of this is not to print something out but to return the thing that's found return sound that's all I need to do forget about all this I want to return found because I want to see it in the console so where else I might call it so that's I just kind of like got confused because I'm typing everything into the console which is a little bit confusing so let's run this again and say tree search 19 and hold on did I not save everything ah okay of course the problem is I need if I want to return a value you know one of the nice things about this digit thing is I was just going through everything I loved it worrying about returning a value so we just call the next function but if I want to I need to return the results of the recursive calls so I need this return and I need this return so this should really fix it so I'm going to refresh this and I'm going to say tree search twelve and now I've got twelve like as I changed it to but I want to return a reference to the full object doesn't really matter but tree dot search five and we can see I got the node now the chance the value fine we know this laptop is kind of covering it so okay so that's how you search the tree and it by the way I search for something that's not in there I'm going to get undefined however I can put this back in just to be sure and I can get null so if what I want to do is you know now actually here I could say you know tree dot search you know 10 let's just see if this tree has 10 in it and and I could say now if result equals null console dot log not found elf console dot log you know result so now I'm going to run this and ten is not in there ten is not in there 10 is on in there how likely is it's going to put Ted and arrow it had one tooth found 10 so you know about 1 out of every 10 times I get Kim stop skipping refresh stop find it find it find it oh oh what's wrong with me okay you guys get the point okay so this is a binary tree whoa hopefully what you see now just to summarize I think I'm going to in a separate video and make a part two where I add some visuals to it so that that's what I want you to be thinking about well why would you this is an important data structure that you can use to store information for binary search for sorting for dictionary of words or so many possibilities but the key thing is what kind of creative outcomes could you have here could you create some type of game which involves a binary tree and you have to add things and find things with swirlix there's the sort of lingo thing I made before it make a binary tree rata specifics to it just visualizing it is there something beautiful in the way that the binary tree you traverse the binary tree recursively could you do some kind of nice animation I think there might be some unique possibilities there so I'm not very good at this kind of stuff any of it really but especially the visual stuff but in the next video I'm going to at least try to draw some of the tree so we can see how it looks if we if we draw for a basic element okay I'll see you there [Music]

Channel: The Coding Train

Views: 294,461

Rating: 4.887536 out of 5

Keywords: JavaScript (Programming Language), live, programming, daniel shiffman, creative coding, coding challenge, tutorial, coding, challenges, coding train, the coding train, binary tree, binary search tree, data structure binary, data structure binary tree, binary tree javascript, binary search, binary search tree javascript, binary tree js, data structure javascript, computer science data structure, intelligence and learning, machine learning

Id: ZNH0MuQ51m4

Length: 39min 7sec (2347 seconds)

Published: Tue Mar 21 2017