Binary Search Tree Insertion

Key Takeaways

okay let's have a look at how to insert some elements into a binary search tree so let's dive right in so first to add elements to our binary search tree we need to make sure that the elements were adding are actually comparable meaning that we can order them in some way inside the tree meaning at every step we know whether we need to place the element in the left subtree or the right subtree and we're going to encounter essentially four cases so lend ensuing an element we want to compare the value to the value of the current node we're considering to do one of the following things either we're going to recurse down the left subtree because our element is smaller than the current element or we're going to recurse down the right subtree because our element is greater than the current element or there might be a cat case that the current element has same value as the one we're considering and so we need to handle duplicate values if we're deciding to add duplicate values to a tree or just ignoring that and lastly we have the case that we've hit a null node in which case it's time to create a new node and inserting our tree let's look at some animation now so on the Left I have a bunch of insert instructions so we have all these values you want to insert into our binary search tree and currently the search tree or the binary search tree is empty so first we want to insert 7 so 7 becomes the root of the tree view with the first node next we want to insert 20 so 20 is greater than 7 so we insert it to the right next we want to insert five so we always start the rear twin or inserting that's an important point so you start the root and then you move your down a tree to figure out where you want to insert the note so we start at the root and then we're like 05 is left and seven so we're going to fit it to the left now 15 start the root go to the right because 15 is greater than 7 then to the left PS 15 is less than 20 at 10 now 4 so 4 is less than seven move left 4 is less than five move left create the new node now we have four again so let's see what happens here so start seven move to the left we move to the left now we've encountered a value that already exists in our treat so as I said before if your tree sports duplicate values as the time to add another node and you would either picked by convention if you want it on the left on the right otherwise you'd do nothing and i'm going to choose to do nothing i want to insert 33 so start the root go to the right give 33 is greater go to the right again now insert two so two smaller than everything in our tree so it would go all the way to the left now try and see where 25 would go so 25 sings go to the right then we're going to go to the right again because it's greater than 20 but we're going to go left now because it's less than 33 and finally say so once left once right and we've inserted everything into our binary search tree so on average the insertion time is going to be logarithmic but in the worst case this behavior could degrade to linear time let's have a look at that so if our instructions are the following insert one two three four five and six so we start at one then I'm going to insert two so that's when we go to the right eight okay now let's insert three well 3 is greater than everything so I have to place the right began now how about four ok force also greater than everything Oh looks like recurring this line now and now 66 is still greater than everything so as you can see this type of linear behavior is really bad and we don't want to create lions like this because if we want a query where six is in a tree if we want to remove five I do anything on our buying your surgery you first need to find the note that's going to take linear time and this is bad that's one of the reasons why people have invented things like balanced binary search trees or self balancing trees which bounced themselves as you insert nodes will beginning to that later but that's it for insertion it's really simple don't over complicate it so the next video we're going to look at removals for binary search trees but also if you want some source code for binary search tree I've implemented one just go to my github repository and look under the binary search tree folder I'm going to be reviewing the code at the end of this series so stay tuned for that guys thanks so much for watching any questions just drop a comment I love reading them alright see ya