Data Structures in Python - Full Crash Course

This video today is a crash course on data structures from scratch in Python. We're going to implement multiple different data structures from scratch in Python to learn how they work to understand them from the ground up. We're going to start with linked lists. We're going to then move on to stacks, cues, hashmaps, binary search trees, heaps, tries, and we're going to finish off with graphs.

The goal here is not to build these data structures so that you can use them in your programs. The goal is to understand them by building them from the ground up. Now, this video is a compilation of eight separate videos that were already uploaded to the channel, but you guys always prefer these all-in-one videos, you prefer to have everything in one place. So, don't be confused if in the videos I'm talking about in the next episode, in the previous episode, I'm referring to just earlier or later in the video.

Now, if you get value from this video, let me know by hitting the like button, subscribing, and leaving a comment in the comment section down below. But now, let us get right into it.

[Music]

All right. So, we're going to start off this tutorial series by implementing a linked list and a doubly linked list in Python today. Now, as I already mentioned, the goal of this tutorial series is to understand the data structures and also the runtime complexities of the operations that we perform on these data structures by implementing them from scratch. So, we're not going to use any packages. We're not going to import any data structures. We're going to build them from scratch in Python using classes.

Now, I'm going to always briefly explain the data structures so that you know what it is about in theory before we implement it. But if you want to have a more detailed explanation, I have a tutorial series or a course you could say on algorithms and data structures. There you can find more details about them. But I'm going to give you a brief sketch of the basic data structure every time before we start coding it. So let us get started briefly here with the linked list.

I'm going to sketch it out. It's quite simple. The basic idea of a linked list is that we have so-called notes. So we have for example, let's say this is a note and this note has a value. For example, the number 10. Now this note also has a pointer or a reference to another note to the next note so to say. And this note then again also could have a value 20 and it points to another note and so on and so forth. They can have different values and at some point some note will have a pointer to none. In Python it is none. In other languages it's a null pointer. Whatever it's basically the end of the list.

So a linked list works like this. You have nodes and one node points to the next node. This node points to another node and so on until we get to the end of the chain until we get to the end of the linked list. And this structure of course means that we have to perform different operations in different ways. For example, if I want to see if a certain value is part of the list, I cannot just jump to that value, I have to uh go through all the values. So in order to see if 30 is part of the list, I cannot just look at the list and see it. I have to say, okay, let's go to the first note. Is it 30? No. Jump to the next note. Is it 30? No. Jump to the next note. Is it 30? Yes, I have 30 in the list. Um, and because of that, of course, this is going to have a runtime complexity which is in O of N linear.

By the way, if you don't know anything about runtime complexity, I would recommend that you watch some video. You can watch my video or another video that explains the basic idea of runtime complexity because I don't want to go into too much detail here on the theory uh in in this tutorial series. But the basic idea is how many steps you need to perform, how the complexity of your uh of your algorithm increases when you increase the input size. So in this case, the list has n elements, so three elements. And in the worst case, I have to go through all three elements to find the element I'm looking for. Because of that, we have a runtime complexity of O of N. Uh a worst case complexity. Uh that's the basic idea.

Um, so that's a linked list. A doubly linked list is the same thing just that we have two pointers. So every note also points to the previous note. So it's basically like this. And then here we have a nonpointer uh or none reference again. So, it's just um it's it's just in both directions. And this, of course, makes it easier to prepend or or to uh to do certain things. Um, and uh and that's that's just the difference here. So, we have two references. We have going into both directions, that's a doubly linked list. And if it's if it's just going into a single direction, we have a normal uh linked list. And this is what we're going to implement in Python. And we're going to also implement a bunch of different operations.

So, for example, I have my code prepared here. We're going to um traverse it. We're going to display it. We're going to see if it contains some values. We're going to calculate the length or we're going to to get the length. We're going to append. We're going to prepend. We're going to insert at a specific position. We're going to delete. We're going to pop a specific index. So, remove an element not by value, but by position. We're going to get and um yeah, that's actually it for the link list.

So let us get started now with a new uh Python file. I'm going to call this linked list py. And we're going to start with the most important class here which is the node itself. So we're going to create a class note. And this class note is very simple. It's just a simple constructor and a nit method where we say we want to have a value. And every note is going to be initialized with a value and a reference to another note. So we're going to say here self do value is going to be equal to the value and self.next in the beginning is going to be none. So every note when we create it is not going to have a next note. That's all a note is a value and a pointer to a next note. But by default this is going to be empty. It's going to be none.

Now that is the note. The linked list is then another class which utilizes the note class. So we're going to say now class linked list and we're going to say that when we initialize a linked list for the first time, we're going to set um we're going to initialize the head note. So a link list has a headnote which is the uh beginning note. We're going to just take this and uh set it to none in the beginning because if the list is empty, we we don't have any any notes in there. So we have none. But once we add a note to the list, the head node is going to be that first note and every other note is going to come afterwards, unless of course we prepend or insert. Um, so we're going to say here self head equals none. And that is actually all we need. We need the head of the list and then we can perform everything uh from the head onwards.

Now um what we're going to do now first here before I go into the other functions even though you know I'm going to implement a couple of functions maybe before we start with the implementation a good idea would be to list the functions that we're going to implement uh without any code yet. So one function that I'm going to implement is the dunder repper function. This is just a representation. This is going to be traversing the list and printing the values displaying the values that are part of the list. So here we're going to just say pass for now. Uh we're also going to implement the contains dunder which is of course going to check if a value exists in the list. This is what I showed you in my paint here um a minute ago. And then we also are going to implement the length dunder or the len dunder which is going to give us the size of the list.

And then we're going to implement a couple of methods uh that are not dunder. So one is going to be the append method. Obviously, this is going to add a value to the list. It's going to add it at the end of the list. Um, so for that, we're going to do pass as well. We're going to also have prepend, which is the opposite. We're going to insert it in the beginning. And this is what I meant. When you have um when you have a doubly linked list, uh, actually I I messed it up. It's not a prepend. The prepend is easy with the uh normal linked list as well because you just have to create a new node and let it point to the uh to the head node and then make it the head node. But if you want to append in the end, then a doubly linked list is useful because you al also have a tail. So you can do that in constant time as well. But we're going to take a look at that here in a second. Uh, so prepend is the opposite. You insert it as the first element. And then we have also the method insert. The insert method um is adding a value to a specific index to a specific position. Um, and then we're also going to have delete pop get. So delete is going to be delete by value. So we provide a value and this value has to be deleted from uh from the linked list. Then pop is going to do that with an index and get is going to give us the value of a specific index of a specific position. And then we're also going to have a simple uh print function which is going to be quite similar to the representation function if not the same. And then finally we're going to have a section down here if name equals main. And here we're going to then create our class and use it.

So these are the methods that we're going to implement. Now if you want to take it easy you can also drop some of them. You don't need prepend. You don't need insert necessarily. Whatever you want to do. It's going to be quite a lot of code here now, but um you can also choose to just implement a couple of them.

I would like to start with the append function because that's the most um the first thing that you want to do with a list. You have an empty list, you want to add some elements to them uh to the list. So, how can we append a new element to a link list? Now, obviously, if the head is none, I just have to set the head to the new note. So, I can already have a case if self.head is none. So if I don't have anything in the list, all I have to do is I have to create a new node and make it the head of the list. So I can say self.head is equal to note value. That's quite easy.

Now what happens if I already do have a head? Well, then I just have to go uh to the next element as long as there is a next element. And at the end when I see that now there is no longer a next element, I just have to create a new node and put it there. So this means I can say something like last equals self. So I start with a head and I say while my last element that I looked at has a next element. So in the beginning it's the head. Does the head have a next element? If yes, go to it. Um otherwise append it already. So if there is a next element, I set last equal to this ne uh next element. So I go further and further into the list until there is no next element. And what I do then is I say last.n next since last. Next at this point will be none is going to be equal to a note uh given a value.

So maybe um maybe I will do this here now with a graphical explanation just to give you the basic intuition. We have an empty list. So what do I do? I create a new note and give it a value. That's my append if the list is empty. Now here my next pointer points to nothing. So what I do if I want to append 20 for example is I go to this I say while this has a next oh it doesn't have one. So what I do is I create a new note here. Now let's say I want to append five as a value. What I do is I go into the list. I see okay it does have a next element. So I set last equal to the next one. Okay. Does this have a next element? No. Okay perfect. Then create a new note and give it five. Now this here definitely has a runtime complexity of O of N. So we have to go through all the elements here necessarily to be able to append it. We don't have a we don't have a reference to the last element. We don't have a tail element. So because of that we cannot just um append it in constant time. We have to go through all the elements to get to the end until we can then append a new element. So this is going to definitely have a runtime or actually I'm not going to say runtime complexity just O of N linear time and this has a worst case complexity which is linear but it also has an average and best case complexity which is linear because you will have to go through all the elements. It doesn't matter it's not a matter of chance or uh how well the data is structured or aligned. It's just you will have to go through all the data. So this is a linear runtime complexity here.

Now the prepen function is quite simple when we're talking about a linked list because all we have to do is we have to create a new note. We have to make this new note point to the head and then we have to make the head uh or we have to make this note the new head. So all I have to do is I have to say first note is going to be equal to a note that has the value that I want to prepend. And then what I want to do is I want to say this first note then should point to the current head and then the current head should be set to be equal to this first note. That's it. This also works if we have none. Uh think about it here again visually. Let's go to my paint. If I have a list like this, what do I have to do to prepend an element? Well, I just create a new note. Let's say I want to give it the value uh 25 for example. And all I have to do is I have to make it point to the current head. And then I have to say, okay, this is now my head. And if I have none, what do I do? I create a new element and I point to the current head, which is none. Still works. So that's quite simple. And this can be done in constant time. The list can be huge and it's still going to happen in the same amount of time because it's the same operation. So this has O of one O of one constant time. So linear time constant time and this also this is worst case this is best case this is average case because every single time when I prepend a node I will have to do this one operation create a node let it point to the head make it the head that's it every time the same um yeah.

The insert is now a little bit more interesting because now we're going for a specific index now I want to say um I want to put it at a specific position now we have one special case here if this position if the index that I'm trying to insert it um into is zero then I can just prepend. So I can say if the index that I'm passing here is zero I can just say self.preend value because then I'm just doing the same thing that I just explained. Otherwise we're going to um to do the following. We're going to say first of all if I don't have a head and I not trying so if if the list is empty and I'm trying to insert at an index that is not zero then this should produce a value error because I'm obviously trying to access a position that doesn't exist. So we're going to also raise an exception here. We're going to say if self.head is none. And since we're not trying to use index zero, I'm going to raise a value error. And this value error will say uh index out of bounce. I'm not sure if the value error here is the correct exception type or error type but let's just do it like this. So self head is none raise value error. And otherwise if the head is not none what we do is we say again last equals self.head and uh we basically iterate using a for loop for i in range. And now we use the index minus one because we don't want to go to the element. We want to go before that element. Um, and we're going to say if last.next is none at some point here before I get to the index that I'm trying to get to, I do the same thing as above. I just copy this and I paste it down here because this is also a problem. I'm trying to go. So if I want to insert at index five, I have to go to one position before that because I don't want to go after the point where I want to insert. So I have to go minus one. But if I at this point at at somewhere somewhere during this process, if I realize that there is no next element, this means that I don't have enough positions to get to the index that I'm trying to get to. So again, index out of bounds. And if that doesn't happen, then I just say last equals last.next. And if the whole loop runs without raising an error, then I have the correct position. So what I do is I create a new note. I say this note has the value that I'm trying to insert. And then I say the new note next is going to be what this note is currently pointing to as next. I'm going to show you why that is visually here in a second again. And then I let this note here, the last note point to the new note.

So the idea here is if I have um, let me just take my drawing tablet here. If I'm trying to insert something at this position here, what do I have to do to do that? Well, I create the note. Let's say the value is 30 here. I create this new note. What I need to do now is I need to ask, okay, what is the note before me pointing to before myself pointing to? So the note that comes before where I want to insert this is 10. 10 is pointing to 20. So I just copy that. Now I point to 20. And now I say, okay, 10 no longer points to 20. 10 now points to me. This is exactly what we're doing in the code here. This is this here. We create a new node. We point this new note to the note that the last uh node was pointing to and we let let the last node point to ourselves to the new note. That is it. And this of course has linear runtime complexity. In the worst case, I have to go um in the worst case I have to go through all the elements because I'm providing an index that's you know n or n minus one. So that's linear runtime complexity.

All right. So now we have the various methods to add elements to um to the linked list. Now let us talk about the I mean we're going to do the representation in the end but let us talk about contains. How can I find out if something uh is part of the list. So this is a true false function or method. This is going to give us either yes or no. Um, and obviously we do the same thing that we do when we do the appending just that we can stop um before that we look for a value and we can terminate. So I think the average case runtime complexity is n / two. So in half because on average you will have to go through half of the list to find a value. Uh, but in the worst case you will have to go through all of the list and you're still not going to find a value. So this has obviously before we even implement this this has um linear runtime complexity. Oh my god what's happening here? There you go. Okay.

So what we do here is obviously same same concept last is equal to self.head and then we say while last is not none. So while the thing that I'm looking at actually has um is a note is not empty. I check if the value of this is equal to oh actually we need to pass we need to pass a value here. So if last value equals that value, we're going to say return true. And um then we're going to otherwise say that we want to go to the next element. So last equals last.next. And in the end, if I never return true, I have to return false. It's as simple as that. So we just do the exact same thing that I talked about. We start here. I'm looking for, let's say, 40, which is not part of the list. So, I look at this element. No. Next. Look at this. No. Next. Look at this. No. Next. Look. No. Look. No. Okay. End of the list. Um, at some point I don't have any um, any values anymore. I get to this none. And then I have to go I have to terminate the loop and I return false. And if I find the correct value in between, I just return true and the function or the method uh terminates.

All right. Uh, now for the length it depends on how you implement the linked list. This is something that you can implement differently. Now if you just implement it the way that we have implemented it right now calculating the length of the list has linear time and it has actually also in the best case linear time because what you have to do in order to count how many elements you have is you have to go through all the elements and increase a count a counter. So for example with a current implementation what we could do is we could say last equals self head counter equals zero while last is not none. We say counter plus= 1 last equals last. next and in the end we return the counter. That is obviously in linear runtime because of course we have to go through all the elements until we get to the last one every single time. So it's not even average or best case in any other it doesn't even have a different uh complexity when we look at the best case or the average case. We always have to go through all the elements similar to append.

However, you can make this constant if you change something about the class. If you for example also keep track of a size. So if you say self.s size is zero uh and every time you perform an operation you update the size which is not going to change your runtime complexity um you can make this constant. So for example every time when I append I can say self do size equals 1 and I can say here when I append this self size plus equals 1 and so on and so forth and I do that every time I do that everywhere. So here I also increase here I increase and with all the delete methods we're going to implement I decrease. Um in this way all I would have to do is I would have to say return selfize and that would make it a constant runtime complexity. You can do it like that. I'm going to now keep it uh like this. It depends on what you want to do. But this is not a bad thing. You know if you're going to access the length uh frequently it makes sense to have a single integer that represents the size. Doesn't really change the runtime complexity of any function of any method. So that is definitely something that you could be doing. But I want to keep the code simple now. So I'm not going to mess with the size. Uh, just to focus on the operation itself. But again you can make this constant by just updating the number every time the size changes.

Um, all right. So let us move on to the delete method. Now the delete method what it does is obviously it tries to find the element. If it finds it, it updates the pointers accordingly. uh in other languages like C you would have to free the memory. In Python you just ignore it. You just let the uh notes point to a different node. Now but what we do here is basically we say again last equals self.head. We start at the beginning and we say if last is not none already. Now if it's none I'm not going to do anything. So I don't even have to have an else branch here. I just say okay if it is none do nothing. Uh, I mean, you could raise an exception, of course, if you want to or an error. Uh, but I'm just going to ignore it. So, if you try to delete a value that's not part of the list, I don't care. We're not going to do anything. Uh, what we're going to do is we're going to say if last value is equal to the value, we're going to say uh self.head is equal to uh last.next. So this is basically if we're finding the value already in the head. Otherwise, if it's not part of the head, we're going to run a while loop while last.ext. I'm not sure right now if this is even a an efficient implementation. I don't even know if we need this if else statement, but yeah, let's keep it like this.

Now, I prepared the code already. Um, so while we have a next element, what we're going to do is we're going to say if the value of this next element, so we're already looking at the next element of its value. If that is equal to value, we have to look ahead because we need to perform the operation now because if the next element has the value that we're trying to remove, we have to skip it. So we need to say last.next, I change this now to the next next element. I'm going to show you that visually here again in a second. And then we break out of the loop.

What's the logic behind this? Um, let let me just again uh make this a little bit uh better here. So, let's remove this here. Let's say we have I don't know doesn't really matter what kind of values we have here uh pointing to none. Uh, if I want to delete the five for example, what do I do here is I look at the next element. So here at 25 I look at 10. Is 10 five? No obviously not. So what I do is I go next at 10 I look at the next element. I see it's five. Okay I want to remove five. How do I do that? All I have to do now in in Python at least if I don't have to free memory is I have to take the pointer that points to five and make it point to what five is pointing to. So I just have to skip the connection here. I just have to say 10 is now pointing to what five is pointing to and it cuts the connection here. This connection theoretically still exists. So again in other programming languages you would have to free this memory. But now the list is 25 10 30 40. So you just cut the connection here and you redirect it to be uh pointing to what five is pointing to already. That's uh that's the idea here. Um, yeah, this is what we implemented. And of course this is going to be in linear time. Why? Because in the worst case you have to go through all the elements to find it. Now this is not the average case. This is not the best case. But the worst case is linear time because chances are you're not going to find a value. Chances are you're going to find a value at the very last position which means you have to traverse n elements.

For pop it's different. For pop we have to do it with the index. So again we have to raise a couple of errors. First of all if self head is none we're going to raise an an error right away. We're going to say index out of bounds. Um, otherwise if the head is not none, we need to go through our iteration again. We need to say self or we need to say last equals self.head um, and we're going to say then that um for i in range again index minus one. We're going to we want to go one element before that remember so that we can skip the connection. And we don't want to be at the element we want to remove. We want to be one before that. So we can redirect the next pointer. Um, here we're going to say if last next is none which means that if I encounter none before I should encounter none it means I don't have enough uh elements in the link list which means I will raise a value error index out of bounds. And um, otherwise I'm going to just go to the next element. Um, and what I do then is I say if last next is none, which means that if the next element is exactly the one that I'm trying to um, to remove. So basically the edge case that it's the last element that is none that shouldn't be none, I still raise a value error. And otherwise, if that's not the case, what I do is I say last.next next is equal to last.next next which is again the exact same thing that we did here. Only difference is I go index wise. So nothing changes here. I have the same logic but I just go okay uh jump one forward. So if I have a certain index I just go next next um index times or index minus one times and then then I'm at the element that is one before the one that I want to delete. If that one that I want to delete is not none, then I just cut the connection to the next one. That's the same idea. And of course, depending on the index that I provide, this has linear runtime. You can see with linked lists, we have a lot of linear runtime complexity.

Um, yeah, forget obviously quite simple. If you want to get a certain value at a certain index, what you do is you say if self head is none, guess what? We erase a value error. Same principle. The concept here is the same. The only difference is we don't do anything. We just return the value. Um, so actually we have the same kind of iteration. We say last equals self. We say for i in range. Uh, now we can use index because we don't need to stop one element before that since we are not trying to perform any operation. We're not trying to change any connection. So we can just say um go to the element to the exact element and then say if last next is none at some point here then we're going to say raise value error index out of bounds and uh otherwise go to the next element. So last equals last.next Next. And if we can do that without any errors, the value I'm looking for is going to be the value of the last note I end up at.

All right. And of course, guess what? Depending on the index that I provide, this is going to have linear runtime complexity. Perfect. Um, so now we only have the print and the representation. And actually it's not really complicated. It's just a styling thing, but it's the same kind of thing. We just iterate over the whole list and we print the elements. So we're going to say here if self head is none, return an empty list or actually a string of an empty list. Otherwise, I do have some issue with my keyboard here. When I press E, sometimes it sends the key twice and sometimes it doesn't send the key. I don't know why that is. I mean it's it's a cheap keyboard but maybe if you know the solution let me know in the comment section down below. Um, what we do here now is we say last equals self head if it's not none and then we iterate again. We say we craft a return string. This return string will start with um with a square bracket and the first value in here let's make this an f string. The first value in here will obviously be the uh self dot or last last dot value. Um, no, not return. Sorry, return is not so good. Return string. Uh, now we're going to just iterate again. We're going to say while last has a next element. What we're going to do is we're going to say last equals last.next. And then we're going to just say return string plus equals uh f string. And we're going to say comma last do value. Uh, and in the end we're going to close this off. We're going to say now we send it three times. Did you see that? Return string. I need to get a new keyboard. I think uh is just a closing square bracket. And in the end we'll return the return string. That's it. And obviously this is always in linear time even in the best case because you have to go through all the elements to display all the elements linear time even in the best case.

Now actually for the print I don't even we're not going to use print. Actually we're not going to do it. We're going to just say representation is enough. So these are the different methods. Now let's see if I made some mistakes while implementing them. So let's go ahead and create a new length list. ll is equal to length list. Now let's append some values. Let's append the value 10. Now let's say we want to have five and we want to have 18 and we want to have 22 and we want to have 29. And then maybe we want to prepend. We want to say prepend uh 100 for example. And then I want to print ll for example. Let's see what this looks like. We have 100 10 5 18 22 29. Looks perfect. Now let's say I want to insert an element. So let's say I want to say ll insert. And I want to insert a value 200 at position one. So after 100. Now this also works. Perfect. Um, now let's say I want to delete the value 18 from the list. Now I got a problem. Okay, there is an issue with the delete function. What is that? Or with the delete method. Okay, I think it's quite a stupid mistake. I think here when we're checking if the value is the correct value to remove, we say that it should be removed. Otherwise, however, uh, we're not progressing. So, we're not saying last next equals or actually last equals last next. I think this is what it boils down to. There you go. So, now 18 is deleted. Wasn't that big of a mistake. Um, now let's go ahead and say ll pop. Now let's pop index one, which means the 200 should be gone now. There you go. And uh, did we have anything else? We had prepend, insert, delete, pop. I mean, we can do get. So if I say print ll get index one and if I say for example print 29 in ll and print I don't know 800 in ll there you go I get index one is 10 I get 29 is in ll yes yes 800 is in ll no So that is how we can implement a simple single linked list.

Now how would we change this to a doubly linked list? Well, we would have to change first of all how the note works. So we would have to say every note now doesn't have just a next pointer. Every node now also has a previous pointer. So self.pre is none by default. And then we also have for each linked list a tail. So self tail equals none. Now this gets tricky now especially because you have to sometimes or the first time you add something you have to make it the head and the tail but then you have to always keep adjusting um both values. So now let's call this doubly length list. Um, now for the representation function it doesn't really matter because to represent this we have to go from beginning to end. The tail is not important. So we can keep this function exactly the same. Same for the contains function. If we just iterate over the list to get a certain position, it doesn't really matter. I think the same is true for the get function. The get function doesn't change at all. And the length function doesn't change. So this doesn't change. This doesn't change. This doesn't change. And this doesn't change because we don't change anything about the list. We don't have to adjust anything. But we will have to change the way the append function works or method works and all the other methods that actually manipulate the content of the linked list.

Now what we need to do here is if we append a value to an empty list, we have to set the head equal to the note. But we also have to say that the tail is equal to the head. So we have to basically say now since we just have a single element the head and the tail of the list is the same. This is obviously the case. However, if we append something to an existing list um, this is easier now because we just have to append it to the end. So we can actually instead of iterating here we can say now uh the last note we we do basically the same thing that we do here with the prepend. We say the last note is now a new note with a value the last note says that it points or has to point now to the previous note which is the actual tail right now. So self.tail I'm going to show this here visually in a second again. um save self.tail next is going to be equal to the last note and self.tail is now the last note.

So think about it that way. Let me get my fancy drawing tablet again. Let's say we have a doubly linked list. I have this structure here. Now of course in both directions and of course we have a null pointer here and a null pointer here. Now we do have some values it doesn't really matter if I want to now append an element. So add an element to the end of the list and let's say we have a uh in the list here we have head and we have uh tail. Um, if I want to append an element all I have to do is I have to create this new element. I have to make it point to the tail as a previous element. The default for the next is null anyways or none. Uh, and now I have to just say that this element here instead of pointing to nothing points to this new node. So maybe to to illustrate this better, I have a new element down here. I let I let it point to the previous element which is the current tail. I redirect the pointer of the previous element for the next element to this new element. This points to none obviously and I then say that the new tail of my linked list is now this. That's exactly what we did here. And this can be done in now we change the runtime complexity. This can be done in constant time similar to the prepent constant time.

Now the same is true for prepend but we need to adjust it. So this is now basically the same um idea but we need to say again if self head is none uh we need to set head and tail to the same thing. So self head is going to be note value self tail is going to be self head and otherwise we do the same thing as before. Uh, so we create first node is node last node or first node next is the head. The head um is set to the first node. But before that we need to say self head next is going to be equal uh or actually no self head previous is going to be equal to the first note. Yeah that's how we do it. And again this remains uh in constant time.

Now for the insert we don't really change much. The whole structure is the same. The only thing is uh I mean all of this stays the same the iteration but in the end we need to also adjust the previous pointer. So we say new node equals node value new node next equals last next but now we also need to say new node previous is equal to last and then last next is a new note. So this just means that when you insert a new note, you need to make sure that when you insert it here, it doesn't just point to the next element, it also points to the previous one. And then you adjust these pointers accordingly as well. Uh, let me just think about this again. Do we do this here? We say new note, new note next is equal to last. Next, new note previous is equal to last. No, actually we need to also set the previous. We're not doing this here. My prepared code is not that prepared, it seems. So, let me think about this here on the fly while I'm um doing this. I think we need to say before we set last next equal to la uh to new node, we need to say last next previous is equal to new node. I'm not sure about this. We're going to see if we run into problems, but I think this is what we need to do because as I said, uh, let's look at the uh graph here. When I insert an element, what I want to do is I want to cut these connections or actually before I cut them, I want to create a new note. I want to say, okay, I want to point as the next element to this note that this is pointing to. I want to point to this as the previous element, but then I also want the next element here to be pointing at me and the previous element here to be pointing at me. And then I want to cut these connections. I think we're doing this now. If not, we're going to notice and fix this. I hope so.

Um, delete. Now here we actually do it properly. Here we actually progress. So uh, let me see do we have to change much? Well when I delete an element I have to delete the next reference but I also have to delete the previous references. Um, so yeah so I also don't have this prepared in my prepared code. Okay. So, we have to do some things here on the fly. Seems like I didn't invest a lot of thought into my doubly link list here. Okay. But if I'm not mistaken, the only thing that we should have to do here is we need to say last next previous is equal to last next. Yeah. And then last next is equal to last next next. Does this make sense? Not sure. We're going to find out. If not, we're going to fix this. This is also a nice experience here. Uh, for pop we do probably the same thing. So we just say iterate that's fine. And then here we say last next is equal to last next next. But before that we do last next next previous is equal to last. Actually I think this is what we need to do here as well. We need to say last next previous is equal to last not to last next. I think. And for the get we don't change anything.

So let's see. Now this is a doubly linked list. We're going to still call it ll. Let's see if all of this still works. First of all, yes, it produces the same results, which is good. Uh, now, how could we get this to fail? Um, by inserting and deleting.

So by inserting all these values. Actually, for the insert, I should also have the case. Oh no, actually I don't have the length. So if I keep track of the size, I can say if index is size, just append. Uh, but that doesn't make a lot of sense here. So let's say instead of appending, we're going to insert. We're going to always insert. Uh, actually, I'm going to append the first one, but then I'm going to insert at position one, for example. Or actually, I'm going to always insert at position one. 10. Or actually, let's use different numbers. 20, 18, 22, 88, 97. That's a zero, not a nine. Then prepend. And then insert again. And then try to delete 18, and try to delete 22, and try to delete five. Then pop one. Let's see if this makes sense.

Okay, you see there's a problem. Noneype object has no attribute previous. Yeah, of course, because we need to also make sure this is now not irrelevant if we have the um if we have a none, we need to make sure that actually we don't try to set previous. So where did I do that? I did that with delete. So here we need to say um if last next is not none, then we want to do this. And here as well, if last next is not none. This was actually not the problem. Last next previous. Oh, this is an insert. Okay. So, new node previous. That is the thing. If last next is not none.

Okay, let's double check this. To see if this is what we would expect, we append 10. So the first element is 10. Five comes after that. So five should be after 10. 20 should be after 10. 18 should be after 10. No, actually not. Let me, let me, uh, let me try to see what I would do manually here to see if this actually works. So it would say 10, then I would say five, and then I would insert everything before that. So it would be 20. So it would be actually 97, 88, 22, 18, 25. Uh, then I prepend, prepend 100. And then what I do is I delete 18, I delete 22, I delete five, and I pop one. So I should have 197, 88, 20. Okay, 10 is not removed. Why is 10 not removed? Or did I make a mistake here? Let me see again. Does pop not work? What happens if I don't do pop? Oh, I forgot to insert 200. So, this actually should work. Yeah.

Okay. Actually, it works because now I would just pop again. I insert all these values. Then I prepend 100, but I also insert 200. So I delete 18, uh, 22, and five. Then I pop 200. Yeah. And then I end up with this. So I hope there are not any more mistakes in my implementation. But that is exactly what you would expect here. So, yeah, this is how you implement a linked list and a doubly linked list in Python. I hope you were also able to understand why the runtime complexities are what they are. Uh, when we talk about runtime runtime complexity, we always talk about worst case unless we specifically say we talk about best case and average case. But yeah, so let me know if you like this in the comment section down below.

All right, so we're going to implement the stack data structure as the second data structure in this tutorial series today. And similar to last time, I would like to start by giving you a brief theoretical explanation of what a stack is and how it works. It's quite simple. This data structure doesn't have too many operations. The basic idea of a stack is we have blocks, let's say, um, that contain certain values, and what we do is we stack them on top of one another. So, for example, here I have the block with a value 10, and what I can do now is I can add a new block on top of it with a value 20, for example, and then I can add a new block on top of that with a value five, for example, and I can do that. And this operation of adding a new block on top is called the push operation. So I take a new block and I push it on top of the stack.

Now, the second operation, the second major operation of a stack is taking the top element and processing it. So, uh, taking, for example, if this is the top element, the five, and doing something with it and removing it from the top of the stack. This operation is called the pop operation. So these are the two major operations. I add a new element on top, or I take the top element and process it and remove it, um, remove it from the stack. So push and pop. And then there's also the third operation here called peak, which is basically just looking at the top element without processing it. So just taking a look, what is it? And that's basically it. And of course, we can also implement things like, uh, print the whole stack, so iterate through it and print all the elements, or things like checking if the stack is empty. But these are the three major operations: pushing, popping, and peaking.

Now, a stack is a data structure that, um, operates according to the LIFO principle. So last in, first out, which is the opposite of a queue. We're going to talk about, uh, the queue soon in this tutorial series. But the basic idea is the element that was added last to the stack will be the first one to be processed. So it's not the same as a queue where the first person that enters a queue is the first person that leaves a queue. It's the last element that was put on top of the stack is going to be the first one that is popped out of the stack. And this has a bunch of use cases which I'm not going to talk about here in this video today. But that is the basic idea of a stack. And this is what we're going to implement now in Python from scratch. Core Python without imports, just with classes and, as I said, core Python.

So we're going to open up a new file here, which I'm going to call stack.py. And, um, the stack now is still going to be based around a node class. So similar to the linked list, we're going to have a node class. Actually, we're going to have the exact same node class, which is going to have a value and a pointer to the next element. In this case, next is the element below the current element in the stack if there is one. So we're going to say class Node, and we're going to define the init method here to take a value as a parameter and to say self.value is equal to value, self.next is equal to None by default. And the stack class now is also, um, similar to a linked list, has a top element, which is, um, similar to the head element, but this element is always just a top element, and we always just work with this element. So we always just either add something on top. So we could say, in, in terms of a linked list, we always prepend, or we always, um, just pop the most top element. We always pop the head, so to say.

So here we can say def __init__, and we're going to say self.top = None. And we're also going to keep track of the size today. So we're going to start with the size of zero because we don't really have to change much when it comes to a stack, uh, and updating the size. So we can easily implement already the length function, which is going to just return self.size. And I don't think it's a surprise when I tell you that this is possible in O(1). So this takes constant time, constant runtime complexity, because we always just have to return a single value, which is updated in the other methods. So that is the length. And we also are going to implement the representation, but not yet. So I'm going to do that in the end. So just pass for now. We're going to also implement the push method, which is going to push a new value on top of the stack. We're going to implement the pop method, and we're going to implement the peak method, and then we're also going to implement the simple is_empty method.

Now, actually, we can do this already. We can just say return self.top is None. That's it. So the important thing about the pop is it actually returns the item. So it's not just popping it out of the stack and then removing it. We also return the item. This is the difference between, for example, the pop, or actually, maybe I should have implemented that also in the linked list like that. But the difference here is that we actually return the value. We want to process it. So let us start with a push. Let's say we want to add a new val element on top of the stack. How do we do that? Uh, well, it's basically just a prepend function of the linked list. So if we don't have a top element, so if self.top, um, is None, what I do is, or actually, I don't even have to do that. I can do that simpler. I can just say, uh, create a new node, and let it point to the previous top, because even if it's None, I just point to None, which is fine. So I can just say here that, uh, my new node is going to be equal to a node that has the value, and then the new node's next should be just pointing at self.top, and then I want to set self.top equal to the new node. So, and of course, we want to say self.size += 1.

So if we look at our graph here, the basic idea is that if I have, uh, let's go back a little bit here. If I have this stack here, and let's say we don't have any dots up here. If I want to add a new element, what I have to do is I just have to create this new block, uh, with a certain value. Now, I, I'm using my mouse. This is why this doesn't look so good. Um, if I say, oh, this looks horrible. If I say this is six. Now, all I have to do is I have to say six now points with the next pointer to the five element, and I have to set the top reference in my stack to this element. That's all I have to do. This is quite simple, and of course, this works in constant time. So this works again in O(1) constant time, and you will notice that the stack operations always take constant time, um, except for maybe the representation here, but they have a very limited use case, or very limited use cases, but they all work in constant time.

Um, so for the pop method, what we have to do is we have to say, if self.top is None, then of course, it doesn't work. I cannot pop an element from an, from an empty, um, from an empty stack. Doesn't work. So I have to say, raise ValueError, and then "Stack is empty." And otherwise, what do I have to do? I basically have to get the value. So I have to say, the value I'm popping here is the value of the topmost element, because I want to return it, right? And then I have to say, self.top = self.top.next. So self.top is whatever the next element is. So self.top = self.top.next. self.size has to be decreased by one, and in the end, I return the pop value. Again, visually speaking, what does that mean? It means that five is my topmost, uh, element here. So what I do is I get the value five, because I need to return it, and then I just say, okay, my, um, top pointer of the stack is now not pointing to five, but to whatever five was pointing to as the next element. So my top pointer is now located or pointing to 20, and I have the value five, which I return to the person calling the function.

Um, and of course, this is possible in constant time, because all I have to do is I have to take the top element. I don't have to go through the stack. It doesn't matter how large the stack is. I just look at the top element and I point to the next one, and I return the value. It's always the same, even if I have a million elements. So constant time. Uh, and peak is even simpler. Peak is just basically saying, if self.top is None, then I can raise a ValueError, "Stack is empty." And otherwise, I can just return self.top.value without doing anything. So I'm just looking at the value, but I'm not popping it out of the stack. And of course, again, this works in constant time, and of course, this as well, this also works in constant time. The only thing that does not work in constant time is if I want to print the whole content of the stack, which usually I don't want to do. But if I want to do that, it takes, uh, linear time, because I have to go through all the elements. So even in the, in the best case, it takes a linear, even in the best case, it has linear runtime complexity, because I have to go through all the elements.

So items = [] and then I'm just going to say current_item = self.top. And then I say while current_item is not None. So while the current item is actually an item, I say items.append(str(current_item.value)). We can do that because we have, um, or actually, can we do that? current_item.value, we should say. So because our node doesn't have a representation function, we have to access the value. So we append to the items list the value, and then we're going to say current_item = current_item.next. This goes as long as I have some value that is not None, or some node that is not None. And then I join all of this together here, um, on commas. This is one way to do that. Last time we did it with, um, crafting a string. This is another way to do that. We got to have variety here. And this, of course, as I said, needs linear runtime complexity.

All right. So, let's see if this works. For this, we're going to open up a section down here. If __name__ == "__main__":. Uh, and what we're going to do now here is we're going to create a stack. We're going to say stack = Stack(). And then we're going to just say stack.push(). Let's push a couple of values into the stack here. Then maybe something like this. There you go. And then print(stack). And then maybe stack.peak(). To see the top value. And then maybe stack.pop(). Which is also something that we can print. And maybe in between, you want to also print the full stack to see what's happening. Maybe I can just take this and copy this a couple of times. Um, and of course, I can also in the end try to see if stack.is_empty(). But that's what we do. We say 12, 6, 14, 10. So this is the stack. Since I pushed 12 last, 12 is the topmost element. So if I print the stack, I get this first. If I peak, I get this first. If I pop, I get this first. And so on and so forth. And, um, in the end, I only have 10. So if I pop one more time, I should probably get an empty stack. Or do I get an empty stack? If I pop one more time, it should then probably crash. There you go. "Stack is empty." Works. And I should also be able to say print(stack.is_empty()). This should give me a True now, but it should not give me a True if I do it up here. And I get True here, False here. Perfect. Works.

So that is how you can implement a simple stack data structure in Python. Next time we're going to talk about the queue, which is quite similar, just that it has, um, the opposite order. So first in, first out. This time we have last in, first out, which means last element to enter is the first to leave. And the queue works the opposite way.

All right. So we're going to implement the queue data structure from scratch in Python today. And as always, I want to start by giving you a brief theoretical explanation of the data structure so you know what it is that we're implementing here. And for this, I want to use my paint again. So in the last video, we talked about the stack data structure. And the stack was just a bunch of blocks of data stacked on top of one another. And we had a top of the stack. So we had a top element, um, of the stack. And the three major operations were: I can push new stuff onto the stack. So I can take a block of data and put it on top of the stack. I can pop stuff out of the stack. So I can take the top element, remove it from the stack, or I can just look at the top, so I can just see what's there by peeking at the stack. And this principle of pushing something on top of it and taking that element as the first element to be popped when we use the pop operation, um, this is the LIFO principle. So this is last in, first out. The last element I push on top of the stack is the first one to leave the stack when I use the pop operation.

Now, the queue is exactly the opposite of that. The queue says first in, first out. So a queue operates according to the first in, or FIFO principle. First in, first out principle. So it's literally a queue like a queue of people. You have a front, and what you can do is you can enqueue elements. So the operation here is called enqueue, like this. And let's say at the front we have a block of data, and then we have another block of data, and another one. If I now want to enqueue an element, what I do is I just put it at the rear end of the queue. So whatever I put into the queue, whatever is enqueued, is added to the rear, to the end of the queue. And when I use the dequeue operation, I take the element from the front. So whatever enters the queue last is also whatever enters the, uh, whatever leaves the queue last, and whatever enters the queue first is whatever leaves the queue first. So it's literally like a queue when you are in a restaurant or something. So this is the first in, first out principle. And we still have stuff like peaking. So we can still look at the next element to be dequeued. We can still do a peak, but that's the difference here. We don't have the LIFO, we have the FIFO principle. Whatever enters the queue first is also the first thing that leaves the queue, and that is a different data structure. This is a different, uh, way of working with data, and it also requires slightly different implementations here.

So let us get started with the code. We're going to create a new file here, queue.py, and we're going to, uh, still base this around a node. So we're still going to say here that we have a class Node, and this node has a constructor which takes a value. So this is going to be the value of the node. Um, and the node is also going to point to the next node. So it's also going to have the next reference here, which is going to be set to None by default. So that stays the same. This is not too special here. Now, the difference between a queue and a stack is that we also now keep track of the rear end of the queue, because we need to append new elements to the rear end of the queue, and we need to pop them out, or we need to dequeue them from the front. So we need to have a front reference and a rear reference, uh, for this to make sense. So we're saying here now, class Queue, and this class Queue has a constructor, and, uh, this constructor says the following: self.front = None, self.rear = None, and self.size = 0, just so we can make the length calculation quite easy. So we can just say, if I have the the dunder length, I can just say return self.size. Now, of course, I need to keep track of the size. I need to increase it and decrease it accordingly. But, um, this is not too difficult here. Every time I enqueue something, I just add one, and every time I dequeue something, I remove one.

Um, besides that, let's also go for a representation dunder. So for the string representation of that, I'm just going to pass for now. So I'm just going to define the methods that we're going to need. We are going to obviously need an enqueue method. So enqueue(self, value). We are going to use dequeue as well. And this kind of data structure is obviously very useful. For example, I have some tutorials where I did that. Um, you have connections or elements to process. Maybe you use 10 threads or 10 processes to, to do something, and you don't want to process the same elements twice. So you have a queue, and the next element to be processed is not from a list where you have to work with the indices. You just take the element out of the queue, and then the next process cannot take the same element because it's no longer in the queue. That would be a, uh, use case for, for the queue data structure. Um, as I said, we're going to use the peak method as well, or the peak, yeah, the peak method. Um, actually, we don't need a value here for dequeue. Sorry about that. And we're going to use something like is_empty, which is optional, but let's just implement it.

All right. So how do we do these things? We're going to do this one later on. Let's focus on enqueuing and dequeuing. Now, enqueuing is quite simple. What we do is we create a new node, and the new node is going to have the value. And what we do with this new node now depends on whether we have something in the queue already or not. So if self.rear is None, this also means that self.front is None, because if I only have one element, it's going to be the same. So if there is nothing in the queue, what I'm going to do is I'm just going to say self.front = self.rear = new_node. So I say the front and the rear are the same object, new_node. If, however, I already have elements in the queue, so else, what I do is I say self.rear.next is going to be equal to new_node, and then self.rear itself is going to be set to new_node. So basically, maybe if we look at this graphically, I'm going to use my mouse now. So this is not going to be very, uh, beautiful. If I have here F for front, and if I have R for rear. If I have nothing, these are pointing to None. If I have one element like this block here, both are pointing to this element. So my front and my rear element are the same. Uh, and if I now add a new node, what I have to do is I have to say that this is still pointing to this here, right? So I have to say that this thing has to point now to the next element, but also I want to reset the pointer of rear. This is difficult with the mouse. Uh, I also want to reset the pointer of rear to be pointing to this new node. So this is exactly what we're doing here in the enqueue method. And of course, don't forget to set the size or to increase the size by one. That's it. That's the magic of enqueuing data.

Dequeueing now is obviously also not too difficult. What we do is we take the element from the front. Now, if there is no front element, we raise an exception. So we don't want to have, um, any call to dequeue if the queue is empty. So we're going to say, if self.front is None. If that's the case, we raise, let's say, an IndexError. Now, I'm always not sure which one of these errors is the correct one, but I think IndexError makes sense here. So let's say "Queue is empty." Otherwise, what I want to do is I want to say, the dequeued value is equal to self.front.value. So I get the value of the first node of the queue. And then I say that my front element should now be pointing to the next element. So I say self.front = self.front.next. This could be None, of course. Um, and now if self.front is, um, None as a result of that. So if I'm actually pointing to None now, then rear should also be None. Uh, yeah, this makes sense. Um, and of course, every time we want to say self.size -= 1.

So again, what's the idea here? If I have, uh, this structure here, now let me actually use my drawing tablet here, because otherwise this doesn't look very, very good. So if I have this structure here, I'm pointing to this as my rear node. This is my front node. If I just take this out of the queue now, I say that my front element is now pointing to this directly. And if I remove this as well by dequeuing it, then my front element of course points to nothing now. So to None, but this one still points to something else. So I also need to make this point to None. That's the basic, uh, idea of what we're doing here. Dequeuing means size minus one. Enqueuing means size plus one. Okay. And peaking is quite simple. All we have to do in order to peak is we have to copy this and basically instead of, uh, storing it, we can just immediately return it. So I can just say return self.front.value. That's it. We don't need to do anything. And is_empty is actually quite simple. We just say return self.front is None. That is the queue data structure. That's basically it. There's nothing too difficult about this. We just have, I mean, actually we need to implement the representation dunder, but that's basically it. You just go through, you don't even have to go through the elements because you just use the front or the rear to do stuff. We're going to talk about the runtime complexities here in a second, but let's briefly implement the representation dunder. We're going to say items = [] and then we're going to say current_item = self.front. We're going to say while current_item is not None, we're going to just, uh, append it to the items list, and then we're going to move to the next one. So, we're going to say items.append(str(current_item.value)). And we're going to say current_item = current_item.next. And in the end, we're going to say return ", ".join(items). I think this should work.

And now let us talk about the runtime complexity. Now, obviously, the length function, the length dunder, has constant runtime complexity because all I have to do is I have to look at the value. I just have to call a single variable. If I have 5 million elements in the queue, this doesn't change. I just have a different number. I just have a size of 5 million, but that's it. I just have to say, okay, look up the value, return the value. So that is obviously in constant time, which is the best thing that you can have. Now, the representation dunder is in linear time. Why? Because I have to go through all the elements. I have to go through every single, uh, node in the queue to get all the elements. So to print all of them, I have to iterate through all of them. So in the best case, worst case, average case, this is an O(N) linear time. And enqueuing an element, these are now interesting because these are the main operations. Enqueuing an element is also done in constant time. Why? Because all I have to do is I have to look at the rear, and I have to append an element. Now, maybe I have to also adjust the front, but that's not really that much of an issue. So this is done in constant time. There is nothing difficult about this. I just have to look at the rear, and I have to append if there is already a rear. Otherwise, I just have to create the first element of the queue. That can be done with the same amount of, uh, effort regardless of how many elements I have. If I have 5 million elements, all I have to do is I have to go to the last one, which I have a pointer to, a reference to. All I have to do is I have to append a new node there. I just have to create the next reference to a new node. Always the same effort. And of course, you guessed it, this is also the case for dequeuing, because all I have to do, even if I have five million elements, it doesn't matter. I just take the first element from the front of the queue and I remove it, and I adjust the front pointer. That's the same action I take every single time, regardless of if I have five, five million, or five billion, uh, elements in the queue. So that is O(1) constant time. Peaking, trivially as well. All I do here is I just look at the first element. I just have to call, uh, or not call, I have to go to the reference and look at the value. That's it. Uh, and this empty is also done in constant time. So you can see that these operations are quite, um, efficient. All of them are done in constant time. The only thing that takes linear time is iterating over all the elements. But of course, if you want to iterate over all the elements, you have to iterate over all the elements, which is N. So, um, this is going to be linear. So that's it. Let us go and try some stuff.

So let's say if __name__ == "__main__":. Uh, and now we're going to create a queue. The queue is going to be a Queue(). And, uh, we can play around now with enqueuing, dequeuing. So let's just say q.enqueue(10). And then I can just say q.enqueue(20), q.enqueue(30), q.enqueue(40), q.enqueue(50), q.enqueue(60). Um, and then I can print(q). I can print(len(q)) to see that the dunder works. Uh, and I can print, or actually I can say, dq_val = q.dequeue() and I can print these elements. Then I can print the queue again, and also the length. And what I get here is I get 10, 20, 30, 40, 50, 60. Then the length of the queue is six, correct. Uh, q.dequeue(). Why is that? Let me see what the problem is here. Maybe I'm not returning. I think I'm not returning, right? Yes, of course, we need to return the dequeued value, otherwise this doesn't work. There you go. I mean, it still pops it out of the queue, but it doesn't show it. So 10, 20, 30, which are the first elements I added to the queue, are the first elements to leave the queue. Now I have 40, 50, 60 left, and three is also the correct length. So there you go. This is the implementation of a queue from scratch in Python.

All right. So we're going to implement the hashmap data structure from scratch in Python today. And as always, I want to start by giving you a theoretical explanation of what a hashmap is and how it basically works before we jump right into the coding. And as always, we're going to do that here in my paint. Now, the basic idea of a hashmap, or also often times called hash table or dictionary, is that we have so-called key-value pairs. So, we always have some key, like key one, for example, pointing to some value one. And every key can only have a single value. Now, values can occur multiple times, but keys are unique. So key two can point also to a value, value one. Uh, but we cannot have key two then pointing to something else. So I could have key three pointing to value two, or whatever. That's the basic idea. We have a key, and this key leads us to the value. This is the principle. This is how it works in general.

The interesting thing about a data structure is, of course, how does this work? And this works with a hash function. This is why it's called a hashmap. And, uh, it works by passing a key into a hashmap, uh, into a hash function, sorry, and as a result, getting an index where to find something. So we're going to implement our own hash function in this video today. But let's, for now, just consider the hash function to be a magic black box. All we do with this hash function is we feed in a key, some key, key one, for example, and as a result, we get a position in a list, in an array. So we get some index. And this is deterministic. For the same key, I'm always going to get the same index. And the idea now is that the key is basically what I input into the hash function to get a calculated result. So I don't have to iterate. I don't have to search. I don't have to go through all the possible, uh, branches of a tree or something. I just calculate an index based on the key with a hash function. Um, and this index then leads me to a position where I can find a value.

So if we consider that we have some basic list here with elements five and 10 and 30, and maybe we also have some strings here like "Mike", and maybe we have, uh, I don't know, some booleans here like True, or whatever, doesn't really matter. We have some elements in the list here. And instead of providing now the index, what I can do, of course, is I can say I have index 0, 1, 2, 3, 4. Instead of saying I want to find the value "Mike", or I want to find a value at index 3, which is of course also, um, simple if you know the index, you can just jump to the index. But if you don't know the index, you have to search. And what we do now with a hashmap or with a key-value pair is, I have this hash function. When I input the key "name", for example, into this hash function, as a result, I get three. That's the basic idea. Now, why do I get exactly three? It doesn't really matter. Let's say I don't have "Mike" in the list, and I want to store the name. So I want to store the value "Mike" with the key "name". So what I do is I feed "name" into the hash function. As a result, I get three. And what I do then is I place "Mike" at this position. That's the basic idea. Why do I do that? Because the next time I want to find "Mike", I want to find the value for the key "name". I just have to do the same thing. Hash "name", get three as a result. And instead of looking through all the positions here to find "Mike", I just know, okay, position three, jump there immediately. So in the best case, or in a good case, in a convenient case, this can be done in constant time. Constant time. Why? Because that's just a calculation here. We're going to talk about this here, but this is just a calculation. I get the key and jump to the corresponding index. I don't have to iterate over the elements. It doesn't matter how many elements I have here. If I have a unique position for every input here, I can just jump there.

Practically speaking, there are some difficulties, and these difficulties are that hash functions produce, uh, different values, or sorry, produce the same values for different inputs. So maybe I have the key, I don't know, "job", or something, and for some reason, again, let's consider this a magic black box. For some reason, when I feed "job" into the hash, I also get three. So this is called a collision. This means that, for example, if I want to store the job "programmer", what's going to happen now is that it's going to recognize, okay, index three, but it's going to see, oh, I already have a value here. And the question is now, how do I resolve a collision? This is called collision handling. So collision handling, and it can be approached in different ways. One way, for example, is if I have a fixed size, let's say I have, for example, here, um, some empty space, some empty space, and then again some value, uh, would be to just jump to the next free, uh, position. So it would be, uh, something like, okay, I already have "Mike" in here. I want to store "programmer" for "job". So what I do is I jump to three. Okay, it's already taken. Let's go to the next one. Oh, four is also taken. Let's go to the next one. Oh, this is free. So let me store "programmer" here. That's the basic idea. I jump until I find a free spot. And of course, what happens now is that if I, uh, want to find "programmer", if I want to find "job", what I do is I say, hash, I see three. Um, I see this is not what I'm looking for. This is also not what I'm looking for. This is what I'm looking for. So I'm jumping again. So practically speaking, if I have a good hash function that gives me good indices for the different inputs, I can expect to have constant runtime on average. However, in the very worst case, what's going to happen is that I have a list with a couple of free slots, and let's say my hash function is very stupid. Every time I put something into it, every single time it produces one, for some reason, for "job", for "name", for "age", for anything that I put in here, I get one as a result. What's going to happen then is everything is going to be placed at one. So I'm going to have stuff like "Mike". I'm going to have stuff like "programmer". I'm going to have stuff like 30 and True, and all this stuff. And every single time I want to look up something, I'm going to land here and have to jump through all these elements to find my element. So in the worst case, I'm going to end up with linear runtime complexity. In the very worst case, I have to go through all the elements until I find my element. That's the worst case. But with a good hash function, we can get an average case of constant time, uh, average case complexity, which is constant.

Now, we here are not going to use this collision handling in our implementation. We're going to use buckets, which means we're going to have lists of, or we're going to have a list of lists. So instead of having slots, I'm going to have lists. And this means that if I now try to input for "name", "Mike", for "name", I try to hash, and I get three. What's going to happen is I'm going to add "Mike" in here. So I'm going to say that my list here now is going to be ["Mike"]. And when I get the new value "job", or the new key-value pair "job", "programmer", and for some reason my hash function gives me a three again, uh, I'm just going to append it to the list. So I'm going to say, ["Mike", "programmer"], and that is going to be how I handle collisions. So I'm not going to just shift it. So to keep the size dynamic, we're going to have these buckets. Uh, but that's the basic collision handling that we're going to do. We're going to have multiple values, and then of course, if I land here, I have to iterate over them until I find the element that I'm looking for. Uh, that's, that's what we're going to do here. Um, this can still, of course, lead to the problem of worst-case linear runtime complexity, because all of the elements can end up in the same bucket, and then you just have a list. Then you just have to, uh, treat it like a linked list and look at all the different elements in there. This was a little bit longer of a theoretical explanation now, but I think it's important to understand how this works and why this works. And now we're going to implement this.

Now we're going to write the corresponding Python code for this. So I'm going to say here, hash_map.py, and we're going to create a class HashMap. So this time we don't have a node. Finally, we have just a single class HashMap. And, uh, what we're going to define here in the constructor is we're going to say, um, a hashmap starts with a capacity. Now, for Python purposes, this is not really that much of a difference, especially with our buckets implementation, because if you use something like C, you would have to, you know, or any language that has, um, that has fixed-sized lists, you have to keep track of, um, of the size, and you need to make sure that you don't exceed the capacity. In Python, it's not really an issue. So in our case, this is just going to be how many buckets we have. But the buckets have limitless capacity. I mean, of course, you have a RAM limitation, but programmatically speaking, I can have buckets that are very long. So the capacity is just going to be the number of buckets in our case. But if you're implementing this in C, you want to take care of the capacity of the size, and you want to resize, maybe if you want to keep this dynamic. But here now, we're going to use the convenience of Python and just say the capacity is the number of buckets. And besides that, I can store an infinite amount of elements in my hashmap. So, self.capacity, and then we're going to say self.capacity = capacity. self.size = 0. The difference here between size and capacity is: capacity is the number of buckets. Size is the number of elements in, um, the hashmap. And then we're going to say self.buckets = [[] for _ in range(capacity)]. There you go. Okay, so that's just the initialization.

Let's start with the basic stuff. Again, we're going to define the methods that we're going to use. So, we're going to have obviously a length method or a dunder length. I'm going to pass for now. Again, I'm going to have a representation dunder. Or actually, we don't need, do we need a representation dunder? I don't think that I implemented one in my prepared code. So, let's actually just print the buckets if we're interested in that. Let's not use the representation, but we're going to use the contains dunder. So, to see if something is part of the hashmap, for this, we're going to do it in the same way that Python dictionaries do that. We're going to see if we have a key, um, present. So, actually, we, we need to also say key here. Um, then we're going to have the operation put. Put means we're putting in a new key-value pair. So key and value are going to be part of that. Uh, then we want to have get. Get means we provide the key and want to get the corresponding value. And then we want to say remove, which is going to remove the value or the key-value pair for a certain key. And then we want to have these typical dictionary methods. We have keys, we have values, and we have items. This is the same that we have in a dictionary in Python. So keys will give us the list of all the keys, values of all the values, and items will give us the key-value pairs. And then we have one important function, the most important function, the black box here, which is our hash function. I'm going to make this private with an underscore here. That's just going to be a helper function that's in the class. And this is going to take in a key and return, um, the index, the position. Now, for this here, you can use whatever you want. It just has to fit certain properties. You need to produce, as a result of this function, you need to get, um, an index that's part of the, um, that's within the capacity. So if you have a hash function that produces values like 5,000 or maybe even with characters in them, that's not what you want to have. You want to have a hash function that gives you an index that's smaller than the capacity. But besides that, it doesn't really matter what you do here.

Of course, it matters in terms of um in terms of performance and runtime complexity, but it doesn't really matter in terms of it works. But of course, an intelligent hash function will lead you closer to the ideal of having constant runtime complexity. And if you use a very bad hash function like always returning zero or always returning one, you're going to have the problem that you're ending up with worse average runtime complexity.

So our hash function is going to be a simple polynomial rolling hash. We don't need to really get into this too much, but the basic idea is we're going to create a string version of our key. So I'm going to say key string is going to be equal to str key. And uh we're then going to iterate over the individual characters, get their ASCII codes because we need to work with numbers. So, we are going to allow um we're going to allow strings as keys as well, but we're going to have to use um we're going to have to use the ASCII codes to do calculations because we need to work with numbers here.

So key string is going to be string of key. And then we're going to say the hash result is going to be zero in the beginning. And we're going to say for every character in our key string, we're going to say that the hash result should be equal to taking the current hash result. So in the beginning zero time 31 plus and then the ASCII code of the character and the most important thing modulo self.capacity.

Why is that so important? Because by saying modulo self capacity we will never get the capacity or larger. We will always have a number that is between zero and capacity minus one. So that is exactly what we need. So anything modulo self capacity will be good or will be functional. It won't be necessarily good but that is what you need as a hash function. So something that gives you a value between zero and capacity minus one um as a result of a key and of course deterministically. So generating a random int between zero and this uh capacity minus one boundary doesn't do it. You need to always get the same result. Um yeah, so that's our hash function here.

And now we can get into the implementation for the length. It's quite simple. Just return self.size which again means we need to keep track of that. Um for contains it's also quite simple because since we're going to have um we're actually we're not going to use the keys function here. We're going to say for each bucket we're going to see if the key is there if if we find the key. So we're going to say here index is equal to self.hash_function(key) and uh we're going to basically go to the bucket. So bucket is equal to self.buckets[index] and then if we have multiple elements in there we're going to just say for key_value_pair in this bucket if key_value_pair[0] is equal to key what I want to do is just return true otherwise return false.

Basic idea is I use the hash function to calculate the correct bucket. If there's just a single element then I'm going to see if that's the correct one. Otherwise I'm going to try to find it. The important thing is when we add something to the bucket, it's always the key-value pair. It's not just the value because then we cannot know what the key, what the correct key is. We need to have both the key-value pair in there so that we can actually compare the keys. Um and in this case I'm just looking for the correct key. If I find it, the element is part of the hashmap otherwise not. So return false.

Um a similar thing can be done for the get function. So the get function is actually exactly the same structure. Only difference here being that we don't return true or false but we return actually the value and otherwise uh we raise a key error. So key not found. So again same idea I get a key I try to find uh or I get the index which is determined by the hash function. I go into that correct bucket and if I find the corresponding key there, I return the value that belongs to the key-value pair. That's it. And otherwise, I see key error because the key that you're looking for is not found.

Um the put also works not too different. But here now, of course, we don't return, we create. So again, we can say we can start in the same way. We need to calculate the correct index and we need to find the correct bucket. But this time we're not looking for something. We're appending something or we are creating something. So we need to say here for i, key_value in enumerate(bucket). So we enumerate all the elements in the bucket. And the idea is if I already have the element in the bucket I want to update it. If I don't have the element in the bucket I need to create it. So I need to append it.

Um, how do we do that? We can use a fancy thing in Python called for-else. I have a video on it if you don't know the feature. This is quite interesting. Um, if you break out of a loop, if you break out of a for loop in Python, um, you just break out of it. But if you don't break out of it, if you leave it without breaking out of it, you can go into an into an else branch. This is a feature of the language. So, I'm going to show this here in a second. Um, if the key is equal to the key, we can update the value of this key-value pair. So we can say bucket[i] = (key, value). So, bucket at the position that we're at is going to be equal to key-value. So to the new key-value pair, the key is going to be the same obviously since we have this if statement, but the value is going to be whatever we pass here. So if it already exists, go there, change it. Otherwise, um, maybe, maybe what we're going to do here now is we're going to break out of the loop um and we're going to append here an else branch. And in this else branch, we're going to say bucket.append((key, value)).

So for those of you who don't know this feature of the Python language, this means that we're only going to get into this else branch if we leave the for loop without breaking. So if I go through all the elements here and I don't get to a break statement, then I'm going to go into an else branch or into the else branch. If I break out of the loop, I'm not going to go into the else branch. Which means basically if there is no key um or if this key doesn't already exist in um in the hashmap, then I'm going to just append it. Otherwise I'm going to update it and break out of the loop. That's uh the idea. And of course, don't forget if you add a new element, self.size has to increase to guarantee that we can do this here in constant time because otherwise I have to iterate and count and if I always just update this, I just have to look it up.

All right. Um, for removing, it's now basically the same as getting, but we need to delete the element if we find it. So, I'm going to just copy the code of the get method here, and we're going to say index, bucket. Again, if you find the key, what we're going to do is we're going to delete or actually before I do that, I need to be able to uh say which bucket element I want to delete. So again, I and then this in enumerate(bucket). Um, and this allows me to say, okay, I'm in this position or at this position where I find the key. And I'm going to say delete bucket[i]. self.size is obviously going to decrease by one. And the important thing again, I want to break out of the loop. If I don't break out of the loop for some reason, it means that I don't find the key. So I raise a key error. So I remove the key from the bucket. And if I don't find it, if I don't ever get to this section here, it means the key doesn't exist. So I raise a key error.

All right. So that's remove, that's the get, that's the put. And these are now not too difficult. All we have to do here is a simple list comprehension because I just have to say [k for bucket in self.buckets for k, v in bucket]. So the key for bucket in self.buckets for um, and then key and you can say value or just placeholder in bucket. So this says go through all the buckets, get all the key-value pairs and give me all the keys. I can copy that. I can paste it down here. Replace this by v. Make this a placeholder. Make this a v. And uh I can also then copy paste this. And here I want to return both key and value for bucket. Key, value in bucket. And that's basically it.

Now let us talk again about the runtime complexities. So for this one obviously I don't think we need to talk too much about this constant. I just have to look up the value regardless of the size. This is going to take the same amount of time. Constant. Always contains now and actually this this belongs now or this is now true for contains, for put, for get, and for remove. They all have sorry, they all have linear runtime complexity in the worst case because of the thing that I explained here with the uh all of them could end up in the same bucket if you have a bad hash function or just very bad luck. Um but otherwise you're going to have a good distribution and because of that good good distribution on average you're going to get constant runtime complexity. So for all of these we have an average of O(1) constant time but a worst case of O(N) linear time and this depends on the quality of the hash function. We can copy this and we can paste this above all these functions. Every time we have to go to a bucket and find the correct slot that is um that is worst case linear and average case constant.

Um, what we should say here and by the way this also uh or actually for this let me just think about this. We go through all the buckets. No, this actually has linear runtime complexity because we have to go through all the buckets, all the elements. So these three are linear every single time. This is not about worst case. This is also about best case and average case. We have to go through all the elements, all the key-value pairs, otherwise we can't do that. So this is linear and um the interesting thing now is I always say here constant and it's true it's like constant in terms of N. So it doesn't matter how many elements, how many key-value pairs I have, uh on average it should be constant but it's not entirely true because what you see here is we iterate over the characters of the string. So technically speaking, this function here is O(K), you could say. So linear in key length, which means that the longer your key is, the the larger the effort or the more effort this function will have. But usually you don't use like extremely long keys. So you can ignore this. We could say practically speaking, we have O(1) if we don't consider the key length. But if you want to be precise about this, the key length, the amount of characters in the key uh influence the runtime complexity of the hash function. And since we use the hash function in every single function here, we should say it's average O(K) if you want to be precise, but O(1) is fine. So constant time.

All right. So let's play around with this. Let's say if name is equal to main. What I'm going to do here is I'm going to say hashmap = HashMap() and now I can put some stuff into there. So I can say hashmap.put("name", "Mike") and I can say hashmap.put("age", 30) and I can say hashmap.put("job", "programmer") and so on. And what I can do then is I can say print(hashmap.items()). And I have a problem here. Capacity of course, yes, sorry. Let's go 32. Uh orc where did I use orc? Oh sorry, ord. So ASCII code ord. What else? Uh list indices must be integers or slices. Uh yeah, sorry. We need to also of course return the hash result. If we don't do that, we know what the index is, but we don't actually return it. There you go. Now it works. So we have name Mike, job programmer, age 30. And we can also see what the internal structure looks like. So I can say print(hashmap.buckets) and you can see in this case I am quite lucky or actually not lucky, this is to be expected, but I have a separate bucket for each of them. Now the more values I add here, the more overlap I will have. So the more I will get into buckets that have multiple elements, especially because I only have 32 buckets. So at the latest point when I have like 33 elements, I'm going to have buckets that have more than just one item, but probably before that.

So to show you how this works or to to see how good my hash function is, what I'm going to do now is the following. I'm going to say um import uuid, which is a Python package or Python module that allows me to create these unique identifiers, which are just strings. And I'm going to say import matplotlib.pyplot as plt. This is now no longer a tutorial about the data structure. Just showing you how well it works. What I'm going to do here now is I'm going to say I want to have a hashmap. This hashmap should have a capacity of 100. So 100 buckets. And I'm going to say now for _ in range(500000):. And I'm going to use um a million elements here. So, I'm going to add a million different keys um to this hashmap and I'm going to say hashmap.put(uuid.uuid4(), 1). So, this is just a long string um and probably unique, most likely. And the value doesn't really matter. I'm just always going to add the same value. But I'm going to place these different um identifiers into the hashmap as keys and we're going to see how well they are distributed. If I have a bad hash function, this is not going to be evenly distributed. If I have a good D a good hash function, it should be like pretty similar.

So I'm going to say here x = [] and y = []. And then I'm going to say for i, bucket in enumerate(hashmap.buckets):. And here now I'm going to say x.append(i) just so I have the bucket number and y.append(len(bucket)). So how long is the bucket i? So that I have the lengths of the buckets I want to plot them as bar plots. So I'm going to say plt.bar(x, y) and plt.show(). And when I run this this is going to probably take some time here. Maybe I should do it with less so we don't have to wait too long. Let me just cut this off. Let's go with um five here and one zero less. Actually, it's it's still running, right? Can I not? Oh, there you go. So, this shouldn't take forever. But basically, what I'm doing is I'm going through all the buckets, through all the 100 buckets, and um plotting how long they are. So, how many elements of the ones of the 500,000 in this case that I added end up in this bucket? And how many of them end up in the next bucket? And if I have like roughly the same height for each bar, this signals that I have an even distribution with my hash function.

So, I don't know what's happening here. Uh, let me just uh let me just run this maybe with even less just to see if it works. Okay, so this was not representative because I didn't use a large amount of values, large number of values. But there is something in statistics called the law of large numbers, which means that the more elements you have, like the larger the numbers, the more you're going to approach, the more you're going to converge to the expected thing. So I think that with this hash function here, the more the more values I have, the more they're going to be evenly distributed. Um, so actually this is not what I wanted to do. Let me add a zero here and see if it it gets better over time. But you see that the distribution of the bucket lengths or the different bucket lengths are not too different, which means that the hash function is decent because there's no bucket that's like super small or super large. It looks like they have a somewhat even distribution. So the runtime complexity here um yeah I mean it depends because of course when we have the size limited we probably have linear runtime complexity divided by something which is still linear but if you have enough capacity you should have constant runtime complexity. So if I make this a thousand it should get better. It should also be faster uh because I have more buckets and I have to do less of the searching of the linear search. But yeah this is fundamentally how you build a hashmap in Python from scratch. We talked about the runtime complexity. I think this is a very important data structure, very useful data structure. Also if you do LeetCode challenges often times a useful data structure. Of course in Python you're going to use the dictionary usually. So just dict dictionary or if you want to initialize it right away here key value this is what we usually um are going to do but that's basically behind the scenes just a hashmap. So yeah.

All right. So we're going to implement a binary search tree from scratch in Python today. And as always I want to start by taking a brief look at the theory and then we're going to get into the coding. For this I'm going to use my favorite visualization tool, my paint. And I'm going to keep it simple here. The basic idea of a binary search tree is that we have uh a root node and we have left and right child nodes. And these can again have left and right child nodes. They don't have to have a child. So they can also point to none, which in terms of visualization we would just not draw this connection. They can also have just one child node. So something like this is also possible. Um, all of this is still a binary tree. Now this is a binary tree in general. This is not necessarily a binary search tree.

Now, a binary search tree also has the property that every key to the left of a node has a smaller key than the key of the node, and every key on the right of a node is larger. So basically, if I have something like 10 here as my key, it means that on the left side here, I can only have key values that are less than 10. So for example, I could have seven here and I could have then again here we have the left node has to have a smaller key than uh this. So I can do something like maybe two. Then on the right side it has to be larger. So I could do something like nine. Then here it has to be larger again. Um, so it could be something like four. And the important thing is of course everything on the left has to be less than seven. So I cannot go ahead and do something like 20 here. That would not be a binary search tree. It means that everything to the left of 10, every single node here, all of this here has to be less than 10. And on the right side, it's the opposite. So here I could have something like 20. And then here again, we have the same idea. I can have something less or I have to have something less than 20, but it still has to be larger than 10. So for example, it would be 15. That's the basic idea of a binary search tree.

Now, some terminology here. These nodes that don't have any children, we call them leaf nodes. So these are nodes that don't have any additional branches going down, not a single one. Um, and this node at the top we call the root node. So that's the starting node of our binary tree. Now a binary tree in and of itself is not very complicated to understand. The interesting part is some of the operations.

Now, searching a value in a binary tree is actually also quite straightforward. So, the basic idea is uh let's add a couple of values here. So, this could be four. Uh, actually, let's make this five. This could be four. Uh, no, actually, let's make this three. And then, uh, doesn't work. Let's do six. Then, let's do five. No, still doesn't work. Let's do four. Would work, right? Yeah, five and three. There you go. So, let's say this is my binary search tree. In order to find a value now, for example, let's say I'm looking for the value six. How do I find the value six? Well, I look at the root node and then I say, okay, is six less than or greater than 10? And of course, it's less than. So, I go to the left. Now, I have seven. Is six less than or greater than seven? It's less than seven. Okay, go to the left. Now is six greater than or uh less than two? It's greater than two. Okay. So let's go right. And here I have six now. So I found the value. Uh, because of that, it's not that difficult to find values. You just have to look at the current value and then go left or right accordingly until you get there. Now of course if I look for a value that doesn't exist like eight for example. How does this work? I go left because 8 is less than 10. I go right because um 8 is greater than seven. I try to go left because 8 is less than nine. But I see there is nothing here. And because of that I conclude 8 doesn't exist in my binary search tree.

Now the keys are used for navigation. What you can do in a binary search tree node is you can also add a value. So for the data structure we're going to see that I'm going to have a class here, Node, and this Node will have a left child. It will have a right child. It will have a key, which is the value that you see here. But it can also uh carry any information. Uh, so I can also have a value here. And the interesting thing about this is that with a somewhat balanced binary binary search tree um I will be able to find things quite quickly because we're going to talk about the runtime complexity in more detail here. But the basic idea is if I have a tree that is somewhat balanced. Now, this one is not very balanced, but balanced means I have um a pretty, you could say, symmetric tree maybe where um it looks somewhat like this. Most of the values are kind of on the same line. Most of the uh leaf nodes are kind of the same line. Uh, I don't need a lot of steps to get to any value. So, if you consider this here, um, we have three steps maximum to get to any value. You have to go this, this, and this level. So to to find a value. So we call this um O(H) runtime complexity where H is the height of the tree. You could say it like this or you could say O(log N) because it's the logarithm, base 2 logarithm of N that is the height of the tree if it is balanced. Now it's not really like this um in the worst case. So that is uh the average case runtime complexity. In a worst case, a binary search tree could actually degenerate into a linked list because if I have for example uh five as a value and then I insert six as a value and then I insert 10 as a value and then I insert uh 20 as a value and then I insert 30 as a value. You can see that I never go left because I'm always adding larger values. And because of that I'm going right, right, right. And this is now just a linked list because it's just pointing to the next node um in the list. But we're going to talk about this when we get to insertion deletion. We're going to need my paint again. But for now, that's enough. We're going to code the data structure. We're going to code some basic functionality. And then we're going to uh discuss the insert, search, and deletion function again uh when we get to them. So let us get started by creating a Python file, binary_search_tree.py. And let's maximize this. Let's zoom in a little bit. Let's call the first class Node. The Node class is something that we use in a lot of data structures. And we're going to say here now that we want to have um a key. And do we want to have a value? Yeah, let's also or actually, let's not set a value. Let's just say a key. We can set the value if we want to. Um, and we want to say now that each node can have a left child node. By default, this is going to be None. Each node can also have a right child node, which is going to be None in the beginning. Uh, the key is going to be set to the key. The value is going to be None. You don't need a value if you don't want one. Um, but the idea again is you want to use something like a binary tree to be fast at finding something because you have logarithmic runtime complexity on average. Um, and because of that, it makes sense when you find something to not just find the key, but also the value behind it. So, it makes sense to have something there. Um, and another thing that we're going to keep track of here because it makes things a lot e a lot easier is we're going to say self.parent. So, instead of just having left and right, we also want to have a reference to the parent so that each node here doesn't just have a pointer um to the left element and to the right element. Now, I'm using my mouse. Um, but it also has a pointer to its parent node. That's uh going to be important especially for uh deletion. It's going to make things easier. Uh, but that's the basic Node class. And of course for the representation we're going to just implement the dunder wrapper. And here we're going to say now want to return uh an f-string containing containing self.key and self.value. That's that. So that's the basic Node class.

And now we're going to implement the tree itself. We're going to say class BinarySearchTree. It's also going to have a constructor. And this constructor is not going to take any arguments. We're just going to say self.root is going to be equal to None. So we have an empty tree. We have no root node. And that's it. Now what we're going to do here now first is we're going to again define the signatures of the functions or of the method. So we're going to implement a contains method which is basically going to be a search. We're going to to see if something exists in uh in the binary tree. So I'm going to say here contains(self, key). We need also a value uh or actually a key. We're always looking for the key even if we're interested in the value. We don't search by value, we search by key. Um, and then we're also going to use a couple of other dunders. We're going to use the iter dunder which is quite interesting. This is basically what allows you if you have let's say we have some some tree. So let's say I define tree = BinarySearchTree() and then I can do for i in tree. Um, what happens when I do for i in tree is defined by this iter. So that is basically what allows me to iterate and we're going to have three different traversal types. So uh we can choose from that but for now I'm going to just pass. Then we're going to also say __repr__. What's going to be the representation of the tree? It's going to be just whatever the traversal returns. But for now, again, we're passing. Then, of course, one of the most important functions is going to be the insert method. So, it's going to take Oh, by the way, we need self here as well. Uh, the insert, we're going to insert a key and a value. Uh, we're also going to have a search method. So the search method is going to allow us to find the value for a given key or to find a node. We're going to get the full node, not just um the value. Um, and then we're also going to have the delete method. This is going to work with a key as well. Um, and then we're going to use traverse as well. Traverse is going to be a method that allows us to traverse the tree in uh different orders. So, we're going to say order is going to also be a parameter here. And besides that, we're going to have a couple of uh private helper functions. I'm going to define them here as well. Uh, just so we know that they're going to be necessary because what we're going to do with a delete function or method is we're going to first uh use the search method to find the node and then we're going to just delete it. So, we're going to have a helper function which we're going to call _delete and um that is going to be called by our delete method here. Then we're also going to need um two helper methods called successor and predecessor. I'm going I'm going to talk about them uh when we get to them. They're going to be important for the deletion process or actually I think the predecessor uh is not going to be relevant but we're still going to implement it just for the sake of completeness. So successor of a given node, then also the predecessor. Again, I'm going to define these when we talk about them when we get to them. Um, and then we're going to define three traversal methods. So these are at least the three that are listed on Wikipedia. This is why I implemented them here. So we have in_order traversal of the tree and then we have also pre_order traversal and we have post_order traversal and that is going to be what we implement in this video today. So we have the constructor, we have the contains method which is just going to be the search method. Uh, we have an iterator, we have a representation dunder, we have an insert function or method, we have a search method, we have a deletion method. Uh, we can traverse in different ways. So this uh this method here, the traverse method will just call these three helper methods here and the delete method will call this method and we'll also make use of the successor and for the predecessor I don't think that we have a use case. Let me just double check. Uh, I think it's just implemented for the sake of completeness. So you don't have to implement it if you don't want to, but we're going to do it in this video today. So let us get started with the most uh or with the easiest one. I think the easiest thing is to just search for a value. So to just see if it's contained in the tree and for that we're going to implement this basic logic that I talked about going left and right until you find something. How do we do that? Um, let's assume that we have values in the tree or that we also don't have values in the tree. What we're going to do is we're going to say the current node is going to be the starting node. So, self.root. And now we're going to just go left or right depending on what key we're looking for until we get to the place where it should be. And if we don't find it there, if we find a None reference there, we're going to just say, okay, um, we don't have that. So, we're going to just return None. Uh, we can also raise an exception if we want to, but we're going to just return None. And otherwise we're going to return the node. So, um, we're going to basically say if the current node that we're looking at is None or the key of the current node is equal to the key that we're looking for. If one of these two is the case, we just return the current node. Why do we do that in both cases? Because if the current node is None. So if we don't have uh oh by the way we need to do this in a while loop because we need to do it all the time until we find um this base case. So this is a little bit like um recursion but but it's uh in a loop. So it's iterating but it returns the moment that you find a key or end up at None. So if you end up at None you want to return the node anyways because it's just going to be None. So you you want to return None since you don't find anything. And otherwise you want to return the node that you found as well because it has the key that you're looking for. So that is the base case. This is the terminating case where we actually return the current node. Otherwise, what we want to do is if the key is less than the key of the current node. Now it's not going to be None anymore because that's already the first case. So if the current node exists and the key that we're looking for is less than the key of the current node, what we're going to do is we're going to check the left node. So we're going to say if the current node.left reference is None, we're just going to return None because what we're looking for should be at the left side at the left child node. It's not there. So therefore, or not just it's not there, but it's a None reference, which means there is nowhere to go from here. So return None. We don't find the value. Otherwise, we're going to make a step and say current_node = current_node.left and then we're going to check again for this in the next iteration. And otherwise, we're going to also say so basically this is the remaining case if the key is larger than the key of the current node uh or actually is that yeah if the key is larger than the current node uh then we're going to say if current_node.right is None return None. Else current_node = current_node.right.

So I always like to show this again visually even though I think a lot of you guys probably already understand this. I want to make sure that everyone can follow the logic. The idea is we have a tree like this one here and I'm looking for a value. I just go left or right depending on if the key is larger than or less than the current key. And the moment I recognize that the key is the one I'm looking for. So when I'm let's say at this node and I'm looking for two, I can just return this node. And if for example I'm looking for three now I'm going to see okay three or actually three is not a good example. If I'm looking for one now um what I have to do is I have to go left but there is nothing left. So I have a None value here. Because of that I just return None because it means I don't find the node that I'm looking for. So that's quite simple actually.

Now the contains dunder is going to be quite simple but it's actually going to be easier because we're not returning the node. So all I have to do here is I got to say current_node = self.root and then while current_node is not None: I go left and right and then I just return True or False. So I say if the key that I'm looking for is less than the current_node.key then I just go and say current_node = current_node.left. Since I don't need to return it I can just jump immediately and if it's None I'm going to recognize it anyways. So then here if the key is current_node.key if it's larger than current_node.key I'm going to say current_node = current_node.right. Right? And if I find uh the key, I'm just going to return True. And if I get out of this loop without returning True, I just return False. So that's quite simple when it comes to contains.

And the question now is how do I get values into the binary search tree? How do I actually insert something? And the idea here is actually quite similar because what we need to do is we need to go left and right until we find the position we want to insert the new node or where we can find a node that already exists and update the value. But then we need to do some extra work. So we don't just have to navigate to the position. We actually have to create a new node there or we have to update an existing node. So in the case of the insert method, we're going to distinguish between two cases. The first case is quite simple. We don't have a root node. So we don't have anything in the tree. If self.root is None, we're just going to create a new node and make it the root node. So we're going to say self.root = Node(key, value) and then we're going to say self.root.value = value. And that's it. That's the insert if it's the first node to be ever inserted into this tree.

Now in the other case I need to navigate to the position where the new node should be placed or I have to navigate to the position where the existing node with this key could exist and then I have to update the value. Now you can also implement this in a different way. If you try to insert something that already exists in the tree, you can also maybe say okay in this case just um in this case just raise an exception because I don't want to allow for duplicate keys. We're going to just say in this case update the value of the existing node. So we're going to say now the root exists. So what we're going to do is we're going to play the game with the iteration again. We're going to say current_node = self.root and then we're going to say while True:. We're going to go left and right depending on uh where our key is. So, we're going to say if the key that we're looking for or that we're trying to create is less than the key of the current node, we're going to do the following. If the current node has a left child node, so if current_node.left um is or actually let's do it the other way around. Let's say if the current_node.left does not exist, that means that now I have the position where I have to insert my node because I am at a node where the key I'm trying to create is less than the key that the current node has, which means I have to go left and there is nothing left, which means that I have to create my new node there. So if current_node.left is None, we're going to create a new node here. So we're going to say current_node.left = Node(key, value) and then this new node that we created should point back to the current node as the parent. So we want to also say current_node.left.parent = current_node. So that is also uh an important reference and then important we want to also break out of the loop. So, we want to say break. Otherwise, if I want to go to the left, but there already is a node there, we're going to say current_node = current_node.left. So, that's the case for the key being smaller than the node's key. Otherwise, elif the key is larger than the current_node.key, then we can just copy all of this here. and replace left with right. So I'm just going to use here substitution left is going to be replaced by right and that's now uh the difference here because now same game we want to go right doesn't exist perfect note update the value update the parent reference break otherwise go to the right and then we have a final case which is that the key is exactly what we're looking for or what we're trying to create in this case we just update the value of the current node. So current_node.value = value and break again. That is the insert logic.

So again, what's the logic behind this visually here? I want to insert a new node. Let's say I want to insert uh the node one or actually let's go with uh can I do eight? Let's do eight. How do I create a node 8 with a key 8? Uh what I do is I go to 10. And I see okay if I want to insert eight I have to go to the left. Uh can I insert it here directly to the left? No, there already is a node here. So I cannot insert the node here because seven already exists here. So go there. See that seven is seven and eight is larger than seven. So I have to go to the right. Can I just create my key here? No. There exists a note. So it's not a None reference. It's nine. Okay. 8 is less than nine. So I would have to go to the left. Can I go to the left or is it a None reference? No, there's nothing here. Perfect. Create a new node. Eight. If the node already exists. So if for example I wanted to insert nine, I can see that this here is nine. So all I can do is I can just update the value of nine. Value update because nine already exists. These are the two cases that we can have. All right.

So that is not too difficult. The most fancy thing here is the delete method which I think actually we're going to talk about next. Yeah, I want to talk about delete next because delete has now three cases that we need to handle differently. And by the way, regarding the runtime complexities, I'm going to talk about them in the end. But for now, I just want to implement the functionality and then we can talk about the complexity of that and the average case and worst case. Um, but I want to talk about or I want to implement the delete method first and the delete method is interesting because we have basically two different uh three different cases and these are the following. So I have a very simple case, the first case where I'm deleting a leaf node. So let's say I have a tree like this. I have 10. Then maybe I have five. And then maybe I have 15 here. Or actually, let's go with 20. So I have more space. Then let's say I have maybe here two. Maybe I have um seven here. And then maybe I have nine here. And maybe I have 12 here. And then I have 30. And then I have 22. 21, 23. I'm just adding a couple of nodes here to also highlight the other examples. Let me delete all of this here. Uh, and then maybe we have 35, whatever. Deleting a leaf node is super simple because I just have to remove the node and that's it. So if I want to remove two, if I want to remove nine, if I want want to remove 21, 23, 35, all I have to do is super easy, cut the connection. So cut it in both directions. Remove the reference from five to two and remove the parent reference from two to five. That's it. Done. That's the most simple case. The second case is I delete a node. Delete node with one child. Exactly. So that would be for example seven. If I want to delete seven because seven only has

A single child. That's super simple as well because all I have to do is I have to delete seven and I have to redirect the connection. So I cut the connection between seven and five again. I cut the connection between seven and nine in both directions as well. And then I add a connection between seven, uh, between nine and five. So I just replace the note I'm deleting with the only child note. I don't have to make a decision here. It's super simple. I just replace seven with nine. So in this case, I just replace this note here with nine. Super simple as well.

The third case is the only one that's kind of tricky. The third case is I delete a note with two child notes. And in this case, now I need to do the following. I need to replace the note I'm deleting with its successor. So that's a new term that we already talked about in terms of function, uh, in terms of the function name. But a successor, the successor note is the first note, or you could say the smallest note that has, or the note with the smallest key that's larger than the key I'm replacing. So in this case here, I'm replacing, let's say, 20. 20 has two child nodes. In order to replace it, I go to the note that is the smallest note that is still larger than 20. And in this case, that's 21. So 21 is the successor of 20. Why? Because it's, uh, because it's, um, in the right tree, the leftmost note. Now, if 21 didn't exist, I would replace it with 22. That would be now the successor. So, I'm replacing it with the smallest key that is still larger than the key I'm replacing. That is how you handle that. So, in this case here, it would be remove 20, replace it with 21, and remove 21 from down here. In the other case, if I didn't have 21, I would say, um, so if, if this doesn't exist here, I would say, uh, remove 20 again. And now replace it with 22. And of course, what happens then is that I have to, uh, also shift this up. So that's that. So we want to replace everything, uh, we want to replace the note that we're deleting if it has two children with its successor.

Now, for the sake of completeness, we also talked about the predecessor. And a predecessor is the opposite. It's basically the largest note that's smaller than the note. So it would be the predecessor of 10 would be nine, because it's the largest note, um, that is still less than 10. So this is something that we're not going to use for anything, but just for the sake of completeness, we're going to implement this as well. But for the successor, it's the smallest node that's larger than the current note. So let's put all of this now into code.

In our delete method, we're going to first find the node if it exists. So we're going to say node is equal to self.search(key). And if the node is not found, so if node is None, we're going to raise a KeyError because we're trying to delete something that does not exist. "Node with this key does not exist." And otherwise, we're going to call the helper method underscore delete onto, uh, the note. Actually, why is this key? It should be note. So we want to call this with a key, but that should actually delete a note object. So we actually want to work with a note, not with a key. So we find a note using the key, but then we want to actually delete the note itself. And what we're going to do now here is we're going to define these three cases. The first case is node is leaf node. The second case is node has one child node. And the third case is node has two child nodes.

So if the node is a leaf node, how do we actually check for this? We say the node.left is None and the node.right is None. If that's the case, it's a leaf node because it doesn't have any children. Um, and in this case, we're just going to check for the special case that the note that we're deleting is the root note. So, if node.parent is None as well, we're just going to say self.root = None. That's the special case. Otherwise, it's not the root note. So, what we're going to do is we're going to say, if we need to determine which note of the parent note this is. So, let me show this visually. Again, I need to use my drawing template quite often here. Um, if I have a note that I'm deleting, so let's say I have 10 here and I have 5 here and I have, uh, 20 here. Let's say I'm deleting 20. If I'm at note 20, I of course have to set the reference of the parent note. So in this case of 10, the right needs to point to None after this. But when I'm at 20, I don't know if 20 is the left or the right child of 10. I only know that if I'm looking at 10, because then I can see left and right. But if I'm looking at 20, 20 just tells me my parent is 10. It doesn't tell me I'm the right child of 10. And because of that, we need to check for this. So we're going to say if node.parent.right is equal to, um, to node, then we're going to say the following: node.parent.right is going to be None after this. Otherwise, node.parent.left is going to be None. And in any case, I'm going to say node.parent is going to be equal to None. Um, again, the idea is I'm looking at the parent. I want to know, am I the parent's right child or am I the parent's left child? Depending on that, I'm going to set the respective reference of the parent to None because this note is now deleted. And of course, I also want to remove the reference from this note that I'm deleting to the parent. So I set this to None.

The second case now is that I need to use an elif here because it needs to be, uh, still connected to the if statement. We're going to say if node.left is None or node.right is None. The reason I can do that here is because usually that would not be enough to check. But since I already have excluded the case that both are None, since I have the if statement here. If I get into this, one of them is None and exactly one of them is None because if both were None, it would get into the if. Otherwise, it gets to this checking here. So if still one of them is None, exactly one of them is None. So I can say that the child node, since there is only one, is going to be node. If node.left is not None, else, it's going to be node.right. So the note that, um, is the child node of the note I'm trying to delete, there is exactly one. So I can determine if it's the left one or the right, uh, one because one of them is None, the other one is not. And again here, I have the special case that the note I'm trying to delete here is the root node. So if node.parent is None, that basically means that the note is the root node because the root node doesn't have a parent. In this case, I have to say that the child node's parent is going to be None as well, because basically if I have, if I'm trying to delete, let's say I have 10, the root node, and let's say I have 20, the only child node of that. If I'm deleting the root, of course, that has to now point to None as the parent because that is now the new root node. So I need to say that first of all, the reference, the reference to the parent has to be set to None. But then also self.root needs to be that child node. Otherwise, um, I just have to do the following. I have to say again, if the node.parent.right is this note that I'm trying to remove, then I need to say node.parent.right is equal to the child node. Otherwise, node.parent.left is equal to the child node. And now we do the following. We say child_node.parent is equal to the node.parent. This is, um, clear. But then we also need to say that the node.parent is equal to None, node.left is equal to None, node.right is equal to None. So this is just killing the note I'm removing. The basic idea here being that my note that I'm trying to delete has a parent. Um, actually, sorry, I need to set this to child_node. Okay, so my note that I'm trying to delete has a parent. So this note is either the right child or the left child of this parent. And what I want to do now is I want to redirect this reference, whatever it is, left or right, to the child node. Since I only have one node, I know which one to redirect it to. So again, maybe before I talk too much here without visualization, the idea is I have 10, 20, and 30. Let's say I'm deleting 20 now. So I need to redirect the reference here. It's the right one in this case. I need to redirect it to this child node. And then I also need to set the child node's parent's reference to the parent that it was before. And then I need to cut all the connections. I need to cut this one. I need to cut this one in both directions. So all of this needs to be, uh, cut. The reason we also set this one to None is because we don't want to check necessarily if, um, if it's the left or right note. I just set all of this to None. Parent, left, and right are set to None. That's definitely going to be true. And I redirect the connections here between parent and new child node.

The last case I have here is that I have two child nodes. And this is now where the successor function or the successor method becomes, uh, relevant. So before we implement this branch, I'm going to say pass and we're going to implement the successor method. It's actually not that difficult because think about it. Uh, I'm not sure, do I still have the drawing here? Yeah, think about this. In order to find a successor of a note, all I have to do is I have to go right once because remember it has to be larger than the key of the note I'm currently at. But then it has to be the smallest possible value. So to find a successor, I go right once and then I go left, left until there's nothing there. So in order to find a successor, I say if node is None, I will raise a ValueError because I cannot find the successor of None. Uh, but otherwise, I'm going to say, actually, I don't need an else branch. I can just do it like this. If the node.right is None, then I don't have a successor. So if there's not a single note that is, that has a larger key than the current node, then I'm not able to find a successor. Otherwise, if there is a right note, I'm going to say current_node is equal to that right note. So go right once and then while we have, while we have current_node, so while that exists, say current_node is equal to current_node.left. And in the end, return the current_node. So again, go right once and then go left all the time. This will inevitably lead to the successor. So if I look at 10 here, what's the successor of 10? Go right once and go left as long as you can. And of course, if I had, for example, 11 here and 15 here, then I would do the same thing. Go right once, left, left. If I'm looking at 22, go right once, left, and go left as much as you can. In this case, there's no room between 22 and 23 if you're using integers, but the idea is go right once to make sure it's larger than the current key, but then go left to get the smallest value possible. Um, that is a successor.

Now, for the predecessor, it's actually basically the same thing in the other direction. So I can copy that. And the only thing I have to change here is I have to go left once and then I have to go right all the time. And that's how I find the predecessor. So that's quite simple. And we said that if we want to delete a node with two child, uh, child nodes, all we have to do is we have to find the successor. So I, I can say successor is equal to self.successor(node). And then all I have to do is I have to say the node.key is going to be equal to the successor.key. The node.value is going to be equal to the successor.value. So I replace the key and the value of the current node with the key and the value of the successor. And of course, if you have other fields here that are relevant in terms of data, so something like, I don't know, some, some file pointer or something, anything that belongs to the content of the note, you want to copy it here. And afterwards, you want to delete the successor. So basically, what's going to happen here is, let's say I'm trying to delete 22. What I'm going to do is I'm going to delete the key and the value of 22. So whatever is in here, I'm going to wipe it clean. And the successor is 23. So what I'm going to do is I'm going to copy the value here, 23, and whatever the value is, like "hello" or something. And then I'm just going to delete 23. There you go. That's, that's the basic idea. And since we have the delete method, this is going to be done properly. So if it's a leaf node, it's just going to delete it. If it has exactly one child, it's going to, um, shift it properly. And it cannot have two children because then I could go left one more time. And, um, yeah, because basically if you try to, if you try to delete the successor, it can either have one child, the right child, or it can have no child. So it's a leaf node. And that is our delete method. So we again, we call it here, we find a node here with a search function. Then we delete this note, and the deletion happens in these three cases.

All right. So the last thing that we need to implement before we talk about the runtime complexities is the iteration and of course also the representation. But the representation is just going to be a string version of the iteration. So let us implement the traversals. And we're going to actually do that here as generators because what I want to do is I want to be able to iterate over it. And because of that, we're not going to return. We're not going to just print. We're going to actually yield. So we're going to yield from, um, the traversal functions. So the in-order traversal is basically you want to go through the left subtree first. You want to go then to the root node and then you want to go to the right subtree. So let us see what this would look like in our example tree here. The in-order traversal is actually quite intuitive. Again, remember we go left, then root node, then right. And this basically means we go left. There you go. Then we go root node. So root node in this little subtree here is five. Then we go right. So we go always, we go to the lowest level. Then here we only have a root node. So we print this. Then we go up. So we have left, root, right. This is a left, root, right. Now, right here is again left, left, root, right, then root, since this is left, then here again left, root, right. And if you look at the numbers, that is why it's called in-order because we go 2, 5, 9, 10, 11, 12, 15, 22, um, 23, 30, 35. So we go in ascending order. This is just the ascending order. Uh, that's why it's called in-order traversal.

Now, the pre-order traversal, um, is root node first, then left, then right. So it would be 10, 5, 2, 9, 22, 12, 11, 15, 30, 23, 35, um, yeah, so that's the pre-order traversal. And the post-order traversal, post-order traversal is now left, right, root. So we go first two, then 9, then five. So 2, 9, 5. Then we also don't go to 10 yet. We go 11, 15, 12. Um, then we go 23, 35, 30. Then we go 22, and then we go 10. So that's the last thing. The root node is always the last thing. Um, and these are the three methods that we're going to implement now. So we're going to go into our code again. And here we actually need to change this now to accept the node argument because we're going to call this recursively. Um, I'm going to explain here in a second why. Uh, the basic idea is I actually already set that while showing the visualization. But every node can be considered a subtree. So if I do the in-order traversal, we said we go left, root, right. We do that on for every node. So if we only have one node, that's the only thing that we can return. But otherwise, we can consider this to be left, this to be right, and this to be root. So first call is left, root, right. And since this is the first one here, I do the same thing. I have this subtree now, left, root, right. And in here, I do the same thing. So I do this, I do root, and then I do here again, left, root, right. And then within this tree again, left, root, right. So this is why we call this recursively.

Now, there is a caveat to this because we're not actually returning, we're not just printing. We actually want to yield the values. We want to generate these values. Now, for those of you who don't know what generators are in Python, I'm going to briefly open up an interactive shell here to show you. Let's say I have a function gen and this function just iterates for i in range(20). Now I don't return these values. I don't print these values. I want to yield them. I want to generate them. So instead of printing them, I can just say yield i. Now, what does this do? What this does is when I create my generator object here, I can iterate over these values. I can get the next value. So I can use the next function onto my generator to get the next value from this loop. And I can also iterate over it. So I can say for x in my_gen and then I can just print x. And this will now no longer give me zero and one because I already used those. But I will get 2, 3, 4, and so on up until 19. That's the idea of a generator. I generate values, I yield values. And we can also do that recursively. So what I do here is I say if the node is not None, um, what I do is I call this function recursively. So I say, or this method, self.in_order_traversal(node.left). So we go again, left, root, right. That's the in-order traversal. So I also do that on right. But in between, I also need to yield the note that I'm currently talking about. So the note that, that is currently my root note here. So I say, um, yield, and then this node's key and this node's value. That is going to be my base yield case. However, I also want to yield whatever I get from here. So in order to yield everything I get from this call and everything I get from this call, we use the syntax yield from. So this basically yields whatever these functions yield or methods. Um, if you're confused by that, if you don't know what I'm talking about, you can watch a video on generators. You can watch a video on yield from. I do have videos on this on my channel, but I'm not going to explain generators now here in more detail. But that's the basic idea here. We want to yield the values in this order. And then I can just copy paste this to my other methods. So I can say in this case, I keep everything the same, but for the pre-order traversal, I yield the node first and then, uh, actually I need to change this then to pre-order traversal as well. Uh, and you need to consider, of course, this order of left, uh, left, center, right is of course then also recursively applied within these function calls. So it's always this, this principle, the same thing that I showed you, um, in, in my paint. And then for the post-order traversal, all I have to do is I have to change this to post-order. Post-order, and this needs to be yielded last. So these are the three traversals. And to actually do a traversal now, I need to call them. So I need to call them here in the traverse method. So we're going to say here, if order is equal to in-order, then we're going to say yield from self.in_order_traversal(self.root). L if the order is equal to pre-order, yield from pre-order_traversal(self.root). And if the order is equal to post-order, I'm going to yield everything from the post-order call. And if I get anything else, I can raise a ValueError, "Unknown order." There you go. So that's how this works. And now finally, we can also implement the iter and the representation dunder. This is quite easy. All we're going to do for the iteration is we're going to say yield from, and then self.in_order_traversal(self.root) is going to be our default. And then we're going to say, yield, uh, here actually not yield from. We're going to say for the representation, we're going to return the string version of the list version of whatever we get from the iterator, so, or not from the iterator, from the generator, self.root. So we call the in-order traversal onto root, we turn it into a list. You can turn a generator into a list, it will, it will just generate all the values and store it in a list, and then we can turn that into to a string and return this. So that is the implementation of our binary search tree.

Now let us talk about the runtime complexities. We already talked about them in the beginning. The basic idea is when I have a tree, my average case runtime complexity and my worst case runtime complexity are different. Now if I start at the value 20 and I go left, right, and I append 10 and 30, and I do that in the perfect balanced way, 5, 15, and, uh, 25 and 35. If I do that like this all the time, I keep the balance by inserting the values in in a specific way, then I will have a balanced tree and the height of that tree will be the logarithm of N. So the height in this case will be the logarithm of N base 2. Um, and I will only have a very small number of levels compared to N. However, if I do it in an unintelligent way, so the same values inserted like this: 5, 10, 15, 20, 25, 30, 35. Now the height of the tree is actually N. So I have as many levels as elements, which is not a good thing. So in this case, I actually end up with a linked list, and this is an actual case. This can happen. So that would be a worst-case runtime complexity of N for basically anything for searching, because if I want to find the value 35, I have to go through all N elements. Uh, for inserting, if I want to insert 36, for example, I have to go all the way to the end. For deleting, if I want to delete 35, I have to go all the way to the end. So in the worst case, I have an O(N) linear runtime complexity. If I want to do this in a balanced tree. So in the, in the, um, average case, if I consider the average case to be the tree is somewhat balanced and I have, um, a height which is logarithmic in terms of N, that would mean that I only have to go, uh, a logarithm of N levels low. So that's a very good runtime complexity because all I have to do now is, in this case, I have 1, 2, 3, 4, 5, 6, 7 elements and I only have, um, two levels, which means that I only have to make two decisions to get to any node. If I want to delete 35, I go right, right. If I want to find 15, I go left, right. I only have to go a maximum of two actions for seven elements. That's, uh, the idea behind this being an average runtime complexity. So in the code, I'm not going to now add all the comments here, but basically for all these things here, except for the iteration and the traversal, the traversal is always going to be linear because you have to go through all the elements. So actually, let me add some comments here. This is always going to be O(N). This is always going to be O(N) because in order to go through all the elements, you have to go through all the elements. So this is going to have a linear runtime complexity. This is going to have O(N) in worst case and O(log N) in the average case, and it will have O(H), so O(height) always. And I can copy this now and put this over insert. I can put this over search. I can put this over delete. Uh, traverse is going to be linear. And these are now just the helper methods. And for the successor, of course, you could also argue in order to find the successor, you have to go a certain, uh, number of steps on average or in the worst case. But these are now the methods. So linear runtime complexity no matter what for the traversals. Otherwise, average case is log N, best, not best, worst case is linear, and it's always linear in terms of height. But the height depends on how you structure the tree. So that's the implementation.

Now let us move on to the actual experimentation. So let's actually see if this produces some problems. If name is equal to main. And now what I'm going to do is I'm going to reconstruct the tree that we're constantly talking about here. So this tree up here. So we insert 10, 5, 22, 29. So let's say BST is equal to binary search tree. And now BST.insert. And I want to insert 10 in the beginning. And let's say the value is always going to be just "hello" or something. You can use different values if you want to, but we're going to say 10, 5, 22, 29. So 10, uh, 5, 22, 2, 9. And then we have, uh, 12, 30, 11, 15. 12, 30, 11, 15. And then we have, uh, 30, 23, 35. Was it 20? Not sure. No, 30. Sorry. 30, 23, 35. All right. So that's the tree that we already have in our my paint sketch. And now we can actually see what happens if I say, um, print, or actually, for the traversal, this is also an iterator. Yeah. So let's say, uh, for i in bst.traverse("in-order"): what does this look like? Print i. We should see all the numbers in ascending order. And in this case, I get a problem because in line 11, I have some issue with the representation. Uh, that is because I have an extra curly bracket here. Now let's run this. And I can see 2, 5, 9, 10, 11, 12, 15, 22, 23, 30, 35. So that works, uh, perfectly. Now let's go for the pre-order. Uh, we talked about what this should look like. So let's actually move this to the left. Let's move this to the right. And we can see now what it does is it says first the root node 10, then 5, then 2, 9. So we have the structure of first the root node, then the left, but of the left, of course, also the first, first the root node. So we go 10, then we go left, but we don't go left all the way. We go first the root node again, 2, 9, then we go right, first the root node again, 22, 12, and then, uh, 11, 15, 30, 23, 35. And for the post-order traversal, it's going to be the same. Post-order, um, it's going to be the root, root node, uh, last. So 10 is the last, as you can see. And you can go through it and see that it works as well. So the interesting thing would be what happens if I now delete something. Now, if I delete, um, if I delete, let's say, what would be an interesting thing to delete? Let's start with the base case. What happens if I delete 9, which is a leaf node? That shouldn't be too difficult. And now, actually, let's go with pre-order traversal to see if this still works. If I delete 9, what happens is I get still 10, 5, 2. I don't get 9 because 9 is deleted, but the rest of the structure works. Perfect. Um, now let us delete not 9, but something with one child. We don't actually have something with one child. So actually, let's append another node. BST.insert. And let's insert 1. The reason for that is I want to have, uh, something that I can check the case with. So I would have 1 here. And in this case, let's also delete 1 again. And, yeah, basically nothing changes. Uh, or actually, sorry, I didn't want to delete 1. I wanted to delete 2 because now 1 should replace 2. Uh, wrong key. There you go. So, now I have 10, 5, 1, 9 because 2 is no longer there. So this works as well. And now, let us go ahead and remove 22. What should happen? Remember, we go right and we should replace it with its successor. It should be replaced by 23. So we should see 10, 5, uh, 2, 9, then 23. So let's remove 22. And we have a problem. So there is a problem with the implementation. Let's fix that. Okay, I found a mistake. We should call the underscore delete method here when we delete the successor and not the delete method itself because this one here takes a key and this one takes a note. So we actually want to delete the successor note that we find here, which means we want to call underscore delete(successor) and not delete(successor). This should resolve the issue. So let's put this here again. Let's run this. And now we can see what happens when we remove 22. 23 moves up. So we have 10, 5, 2, 9, and then we have 23. So of course, this doesn't exist anymore. Um, so 22 was replaced by 23, and then we go on with, uh, 12, 11, 15, and then 30, 35, because we don't have 23 here anymore. So that works perfectly fine. And we can also print the tree itself, which is just going to give us a list of the pre-order elements here, or not, not pre-order, in-order sorted elements here. And, uh, besides that, I think we tested everything. I mean, the search, we could try to search, um, print BST.search and then give me the value of 30. In this case, it's just going to give me the note with 30, "hello". So, yeah, this is how you can implement a binary search tree from scratch in Python.

All right, so we're going to implement a heap data structure from scratch in Python today. And as always, I want to start by giving you guys a little bit of a theoretical understanding of the data structure before we get into coding. And a heap is a tree-based data structure, similar to the binary search trees that we talked about last time. But it has different properties, different operations, and also different use cases. So in a heap, first of all, we have two different types. We have a min-heap or a max-heap, and depending on that, the order is reversed. But basically, we have a top element which is either the minimum or the maximum of the data structure. So for example, if it's 10, all the values below 10, so all the values in the nodes below this, this, um, top node here in a min-heap would be larger than 10. So for example, they could be something like 20, 30, 40, 60, 50, uh, 35, whatever. It doesn't really matter, but all these values are larger than 10. So the minimum element is always at the top. And this is, by the way, true. If this is a heap, if this is a min-heap, then all the subtrees here are also min-heaps. So you can see that 30 is smaller than 50 and 35, and 20 is smaller than 40 and 60. So all the subtrees in a heap are also heaps. And if it's a max-heap, it's the other way around. So it would be, for example, five, uh, three, two, one. I mean, if we allow for duplicate elements, we could also have, uh, three here, but we basically have this structure that the topmost element of each heap, so also of the, of the sub-heaps here, has to be either the largest or the smallest element. So it's not like in a binary search tree where everything to the left is less than and everything to the right is greater than the value, but everything below this node has to be, um, larger or smaller than the value that we're talking about, depending on whether it's a min-heap or a max-heap. And this is very useful to implement a data type, an abstract data type, which is called the priority queue. Now, the priority queue itself is not a data structure. So it is a thing, an abstract data type that can be implemented very efficiently using a heap. So basically, the element with the highest priority or with the lowest priority would be at the top, and then we could just get the next most important element. And for this, we basically have two, uh, two, uh, operations that are important. For example, if I have now here again 20 and 30, and then maybe I have 25 and 40, and then maybe I have 50 and 32 or something like this. How a heap works, how a min-heap works in this case is I can extract. This is the method. I can extract the minimum of this, uh, min-heap. So I would get 10 out of the heap. I would process it if it's a priority queue, for example. And then what happens is I remove this node. So I don't have the root node anymore. I don't have the top node anymore. So what do I do in a heap? What I do is I take the last element. We're going to talk about what last means in a second here. I'm going to show you how this works, uh, in terms of calculation because we're actually basing all of this around an array full of values. Um, and the indices determine which node or which value is the child of which other value. We're going to talk about this here in a second, but basically what we do is we remove the top node. Then we take the last node, we put it at the top. So we basically take the last node here, we remove it from the end, we put it at the top, and now this is of course an invalid heap. This is no longer a min-heap. And what we do is we do a so-called sift-down operation, which means that we look at the two child nodes and we determine which one is the smallest. So in this case, 20 is the smallest of these three. So we swap the position with 20. And in this case, what would happen is we would get 20 up here and 32 down here. And then we look again. Okay, what's the smallest one of these three? We see it's 25. So we replace 25 with 32 and vice versa. And now this is a valid min-heap again. Now, theoretically, if I had some elements down here like 500, let's choose some big number, 600. Then I would make the comparison and see that this is already the smallest element. So I'm done. So I don't have to go down. Um, I mean, actually, this, this wouldn't be possible here because we would have some values here. But, uh, the idea is that you stop when you have, uh, when you are already the smallest value. That's the basic idea. Uh, we're going to talk about this more when we implement it. The second idea is what happens when I add a new element. What happens when I add a new element? Let's say, for example, here I have, uh, 36 now again or something like this. And now I add a new element. What happens is I append it to the heap just at the next free slot. So you can, you can consider the slots to be like this. We have the first one, the second one, the third one, four, five, six, seven, eight, nine, ten. So this is how it's ordered. I'm going to talk about this here, as I said, in a second when we talk about how this works as an array. But, uh, basically, you input some element. Let's say, for example, I input the element, uh, 23, or actually, let's go with something that will end up at the top. Let's go with five. And what I do now is I sift up the element. So now we don't do, we're not doing a sift, a sift-down operation. We're doing a sift-up operation, also called a swim operation. So we're comparing with the parent node, which one is larger, which one is smaller, and then we're replacing them if necessary. So in this case, five, of course, is smaller than 32. So we replace them. Five is also smaller than 25. So we swap them. And five is also smaller than 20. So we swap them as well. And now we have a valid min-heap. Again, that's the idea. So for extraction, we take the top, we replace it with the last element, we sift down. For deletion, we, sorry, for insertion, we, um, insert at the end, and then we just sift up until we are at the proper position.

Now, how does this work as an array? So how this works as an array is that I have an array with all these values and the indices are calculated as follows. So the root element is always, or the top element is always the first one. So I have five. Now, the two children of five are 20 and 30. So they are the next elements. And the children of 20 now are the next elements. So I would have 25, 40. So these are the children of 20. These are the children of five. Now, the children of 30 are the next in the list. So they would be, is this actually, this is 50, right? So we would have 50, 36. Uh, and then we have the children. So, so these are the children of 30. And now we have next the children of 25. The children of 25 is just 32. And that's it. So that is our array. Now, instead of just understanding this visually, we can also put this into a formula. So the, uh, parent element is the same as saying 2 * the index of the element + 1. And the right child is 2 * the index of the element + 2. So if you consider that to be index 0, where do I find the left child of five? 2 * 0 + 1 = 1. Okay. Where do I find the right child? 0 + 2 = 2. Okay. Where do I find the right child of this? It's index 2. So it's 2 * uh, 2, which is 4 + 2, which is 6. So 3, 4, 5, 6. There you go. 36 is the right child of 30. As you can see, this is how you calculate that. The other way around, we could say that the parent of an element, if you want to know that, is, um, the index of the element that we're looking at right now, minus 1, floor divided by 2, if it's not 0. So if the index is not 0, because then of course we don't have a parent element for the first element. But basically, if I want to know, okay, what's the parent element of 50? This is index 5. So what I do is I say 5 minus 1 is 4, divided by 2 is 2. So the parent of 50 is 30. That is how we do that. So all of this can be represented in an array in a simple list. We don't need to work with nodes or anything like that. We can just do index calculations. So that's it for now. Let's get started with the coding and then we can go and discuss more details as we implement the functionality. So let us go to the current directory and here now we're going to create a new file called heap.py. So now we're actually going to have just the heap class. We're not going to have nodes. I think this is the first data structure where this is the case. So we're going to implement a min-heap. Now, uh, again, I'm not sure if I talked about this, but the max-heap would be the other way around. So we would have, uh, 50 at the top, and then we would have values that are less than 50 at the bottom or below 50. Um, all right, so min-heap, let us get started with the initialization. The initialization is going to be, so the constructor is going to be just the heap is going to be an empty list. And then we're going to implement the following functions. We're going to have a length function, so a dunder method. We're going to have a representation dunder. We're going to have the method insert where we're going to be able to insert key and value. By the way, uh, this is something that I didn't mention. Um, all of this that I showed you here is just regarding the key. Every element here that we have can also contain an arbitrary amount of payload or value we can say. So 5, 20, and so on. These are just the values for the heap to be able to structure the elements. But each of these could have, uh, a package attached to them. So here we could have some string "hello" for example, attached as a value to this thing. Uh, and here we could have some value "world" attached to this thing. So it doesn't have to be just a value, it can also contain a payload, which is why we are going to insert key and value. We're going to insert tuples, and we're still going to focus only on the key for the whole operation, but we're going to be able to do that. Uh, then we're going to have the operation peak minimum, which is going to be the same as extracting, but we're not going to actually remove it. So we're just going to show it. So peak min key, or actually, sorry, not key, peak min, and this is going to return the key-value pair. Uh, then extract min, which is going to actually do the extraction. It's going to actually remove it from the heap. And then we have to do the sift-up, sift, sift-down operation, actually, not sift-up. Um, and then we're also going to implement the following methods. We're going to implement heapify. We're going to implement, uh, melt, which is going to be combining the heap with another heap. So we're going to have here other_heap as a parameter. Uh, and here we're going to actually pass a list. So elements, uh, to, to summarize, heapify will mean we get a list of elements, doesn't have to be sorted, doesn't have to be structured in a certain way, and we take that and structure it so that it becomes a heap, so that we actually get this array structure here that we talked about. Um, and then we're going to have the helper methods that we talked about. We're going to have a parent method, which is going to take an index as input and return the parent index. We're going to have the left helper method, which is going to take an index and give the left child of this index. And we're going to have the right helper method, which is going to do the same thing for the right child. And then the most important methods here are going to be sift-up, sift-down. So sift, um, up a specific index and sift-down a specific index, which are also called, as I said, maybe as a comment here, this

is called the swim operation, and this is called the sync operation. And as always, don't worry, we're going to talk about the runtime complexities of all these things at the end, but I want to implement them first before we talk about the complexity, so you understand how this works.

So for the length, it's quite simple. We just return the length of self.heap. That's not too complicated. Uh, for the representation, we can also just return the string version of the list. So this is quite easy. We just show the list, and that's it. Show the heap, and then you can look at the list. If you want to visualize this as a tree, go ahead and implement the logic to do that. I'm just going to print the heap.

Um, and now let us start with the insert method because that's actually quite simple, even though the logic that makes it uh more difficult is going to be inside of these methods here. So for the deletion, for the insertion. But remember, all we have to do to insert a new element in a heap is we have to add it to the end and we have to then sift it up. So we're going to say here, `self.heap.append(key, value)` and then just `self.heap.sift_up`. Oh, sorry, not `self.heap`, `self.sift_up(index)`, which is going to be the length of `self.heap` minus one. So remember, for the insertion, all we need to do is append the new element here, and then it's going to not necessarily be at the correct position. Sift it up the tree wherever it has to go, and this is always going to be the last element. So length minus one is perfect to index it. So the logic will be implemented here in `sift_up`.

Um, `peek_minimum` is also quite simple functionality. All we have to do is we have to say, if `self.heap`, or actually, if not `self.heap`. So if the heap is empty, if we don't have elements, we're going to raise, let's do an `IndexError` because we're going to say "empty heap." And otherwise, we just want to get the first element. So just return `self.heap[0]`. That's going to be the minimum element. It's always going to be the root. It's always going to be the top, the first element. Because of that, just return it without doing anything else.

For the `extract_minimum`, we can start in the same way, but we have to do it differently because now we're no longer just, um, showing the element. We're not just returning it. We actually have to remove it. We have to extract it from the heap. So we can say `min_value` or `min_element = self.heap[0]`. That's the same as before. But instead of just returning it, we now say that the last element of the heap is `self.heap.pop()`. So either you can access it in the same way by saying `len(heap) - 1` or you can just use `pop()`. This gives you the last element. So it pops out the last element. If you do it with the index, you have to remove it with the `del` keyword or with the `del` keyword. But with the `pop()` function, you just pop out the last element. You take it. And what we're going to do now is we're going to say, if `self.heap`, or actually, we don't need to do that because we already checked for that. Or no, we actually have to do that because by popping the element, it could end up, uh, being an empty list. So, for example, if I have, if I have just one element in the heap, which is 10, if I pop it, I could have now an empty list, which means that I need to do it differently. Otherwise, I just remove it, right? And I don't need to do anything. But if I have elements left, so if there is something left in the heap, I need to say that the, um, heap at the first position, the root element, now becomes the last element. And then I want to sift it down. So `self.sift_down(0)`. And in the end, of course, the most important thing, we're going to return the element which we extracted.

So again, visually, what are we doing here? We're saying, okay, I'm removing five from the list. So from the heap, what am I doing? I'm removing this node and I'm returning it. So here, return five. But what I need to do now to restore the heap is I take the last element, so 32, and I put it at the top, 32. And then I check, I sift it down. So I compare this again. Okay, this is now 32. This is now 20. Then I replace it. Also here again, this is now 25, and this is now 32. There you go. Heap is restored. So that is what we're going to do. So we're sifting down the element. Insert and extract are going to use that.

So let us go ahead and implement these. Now, uh, but before we do that, let us briefly implement here the parent, left, and right, uh, formulas. These are exactly what I showed you here. So right is `2 * index + 1`. Right, uh, right is `2 * index + 2`. Left is `2 * index + 1`. And parent is `(index - 1) // 2`. Of course, there are some conditions here. So, for example, maybe the node doesn't have a right child. In this case, we would go out of bounds, and we don't want to do that. So, uh, we need to return in this case `None`. So, we are going to say here for the parent, return `(index - 1) // 2` if the index is not zero. Otherwise, we don't have a parent because that's our root element or top element. Uh, for the left, we say return, or actually, let's say, uh, `left = 2 * index + 1`, which is the formula that we talked about. And now we're going to say, return `left` if `left` is in bounds. So if `left < len(self.heap)`, otherwise return `None`. And the same goes for right, just with a different formula. We're going to say here `right = 2 * index + 2`. So that's that.

Now let us implement the `sift_up`. The `sift_up` is just comparing to the parent and moving up if the parent is, um, if the position is is not correct. So if the parent is small, if, if the parent is larger than me, then I have to move up because I belong further up into in the hierarchy to make this a valid heap. So we're going to say here, the parent index for the current index that I'm trying to sift up is, um, `self.parent(index)`. And then what I'm going to do is I'm going to say, while `parent_index is not None`. So I'm not reaching the top of the heap. And also, in addition to that, `self.heap[index][0] < self.heap[parent_index][0]`. So index zero, since we're passing tuples, remember when we insert, we insert, uh, key and value. So in order to compare the keys, I need to access the zero elements. So the index zero, um, if that value is less than the value of its parent, its parent, they should swap. So if I'm smaller in a min heap than my parent, I belong up and the parent belongs down. That is the rule of the heap. So `self.heap[index], self.heap[parent_index] = self.heap[parent_index], self.heap[index]`. All right. And the index is then equal to the parent index because what we need to do next is we need to move up and do the same thing. So if I swap positions with my parent, now I'm at the index that my parent was at. So I need to reset this and I need to calculate the next parent index. So the `parent_index = self.parent(index)`. And I continue to do that until I'm either no longer smaller than my parent or until I don't have a parent. And then I have the heap property restored.

So now let us move on to the `sift_down` operation. Here we need to do the opposite. So we are placed at the top of the heap. So we're assuming we are the smallest element in the heap, which is most likely wrong. And now we're going to find our way down by always replacing ourselves with the smallest child node that we find. So, uh, we're going to say here, let's remove this, uh, `while True`. And what I want to do now is I want to find the smallest index. So, it's either going to be me, then I don't have to change anything, or it's going to be one of my children. So, either the left one or the right one. I need to know which one it is. And then I need to swap positions with this node. So, I'm going to say here, um, `smallest = index`. I'm going to assume by default I am the smallest. And then I'm going to say that my left child is located at `self.left(index)` and my right child is located at `self.right(index)`. And then I just need to make the comparison. So first of all, if I do actually have a child, so if `left is not None` and `self.heap[left][0] < self.heap[smallest][0]`, then I need to swap positions. So if `self.heap[left][0]` is less than `self.heap[smallest][0]`, then I need to go ahead and swap the position. So I need to say `smallest = left`. I'm going to swap them in the end, but we're going to say now that the smallest one is, uh, located at the index that the left one is located at. And then I can just repeat the same thing for right. And it's going to also compare it to the left child because if the left child is actually smaller than the parent, then, uh, it's also going to be stored in `smallest`. So I also do that comparison. If `right is not None` and `self.heap[right][0] < self.heap[smallest][0]`, then replace this by `right`. So at the end of this, we're going to always have the `smallest` variable pointing to the index or having the index of the smallest node of the, of the node with the smallest key value. So I need to check if this node is myself. So if `smallest == index`, it means that I didn't enter these `if` statements, which means that we're done. I don't have to change anything. So in this case, just break out of the loop. Otherwise, make the replacement `self.heap[index], self.heap[smallest] = self.heap[smallest], self.heap[index]`. So we just swap the positions with the smallest element, and then we, of course, need to progress the index. The `index = smallest`. And I repeat the process. So this is again the same idea that we had here. Uh, it's just the sifting down. I, um, I remove 32, which means 36 is now at the top because I take the last element, and now I sift it down. I look at left and right. Okay, this one is smaller. So I swap the position, 36, 20. Then I look left, right. Okay, it's 25. So I swap this with 25, 36. So that is what we're doing here. All right. So that's actually it. Once we break out of the loop, the heap property is restored again.

And the only two methods now that we need to implement are `heapify` and `meld`. Now, `heapify` again means we take a list of values. We take a collection of values and we absorb them. We structure them as a heap, and we, yeah, we basically reorder them so that they fit the heap property. This can be done quite easily. What we need to do is we need to say `self.heap = list(elements)` in case we get any other, uh, collection format here. And then we're just going to reverse iterate. We're going to start from the last parent node and we're going to just sift down all the elements so that we restore the heap property in all the sub-heaps. And we do that from right to left. So basically from the bottom up, we sift down all the elements. Now, the leaf nodes are already, obviously, trivially valid heaps because they are just a single node. But then we just go from right to left, from bottom to top, and we restore the heap property. So what we're going to do here is we're going to say, for `i` in `reversed(range(len(self.heap)))`: and we're going to go, uh, to `self.parent(len(self.heap) - 1) + 1`. Um, and, uh, the basic idea here is again, we go to the last position, the last element that is part of the heap. We go to its parent. So that's going to be the last parent because that's the first node where it makes sense to even sift down. And then we're just going to call `sift_down` on all these indices. So `self.sift_down(i)`. There you go.

Um, and for the `meld` method, now all we need to do is we need to create a combined heap. So that's not the same as merging, by the way. Uh, because I think merging preserves the order. I'm not sure about this, but I think, uh, melding just basically throws them together and makes a heap. So the `combined_heap = self.heap + other_heap.heap`. And then we're just going to say `self.heapify(combined_heap)`. So we're just using the method that we just defined. Um, and one thing that you can optionally do, I think, um, also with merging, what you do is you keep, I think you keep also the other heap existing. And in the case of `meld`, I think what you do is you say `other_heap.heap = []`. So you basically really absorb the elements from the other heap. But I think you can implement this, um, however you like, depending on what you want to do with that.

So now let us talk about the runtime complexity. This is kind of interesting because, uh, we have different runtime complexities here in a tree-based data structure. Again, we're going to be working a lot with logarithms. So for the insertion, obviously, we have a heap, uh, in order to just add an element and sift it up. What do we need to do? Well, we do have a heap, and the heap is always going to be balanced. So we don't have anything like in a binary search tree where I can have some linked list-like structure. It doesn't work like that. I'm always going to have, uh, a balanced tree because I will never append something not to the next free slot. So I'm always going to have, uh, logarithmic time when I'm looking at the height. So in the case of a heap, O(h) is always O(log n). So this is different compared to, um, to the binary search tree where we could have imbalances, and then we would have to go very long into a direction, and maybe in the worst case, we have all of them lined up into one direction, so we have a linked list. In this case, this can happen. So what we need to do in the case of an insert is we just append at the end, and then we just compare, we compare how many times, height times in the worst case, which means that the worst thing that can happen to me is I append a node at the very end, and then I have to shift it all the way up to the top, which would mean I have to go through all the levels, and the levels are logarithmic in terms of n. So the runtime complexity of insert is always O(log n). I mean, in the, in the worst case, and not necessarily in the best case. In the best case, I just insert and it's fine. So done. But in the worst case, I have logarithmic runtime complexity.

Now, `peek` can be done in constant time because I just have to peek at the top element. Done. Extracting does not work in constant time because we have the `sift_down` operation. Um, so this works again in logarithmic time. What's the worst thing that can happen? I take the last element at the top, or to the top, and I have to sift it all the way down to the bottom. Worst case, logarithmic runtime complexity.

Uh, `heapify` in this case, at least in our implementation here, is linear time because I have to go through all the elements. Um, I mean, not exactly all. I don't consider the leaf nodes, but I have to go through all the elements and perform this. But also, each node is sifted down only once in the worst case. So I will not end up in a position where I have to do this worst-case runtime complexity, which is, as we talked about, logarithmic in terms of n. I don't have to do this n times. So it's not going to be n log n because in the worst case, I'm going to always have to only sift down every node once because I'm going from back to front, which means that I won't have the case that I start at the top and go all the way down. This is not going to happen. Um, so this is linear runtime complexity here.

The `meld` also has a linear runtime complexity because all I'm doing here is I'm adding the two lists together and then I'm, you know, heapifying, which has linear runtime complexity. This here can be done in constant time, obviously, it's just a calculation. Same goes for `left`, same goes for `right`. And these, as we already talked about them, in the worst case are logarithmic. And because of that, also insert and delete are logarithmic because I just have to remove. I can extract, of course, in constant time. I can also append in constant time. But the sifting up and down in the worst case, uh, can take logarithmic time runtime complexity. So I have to go through the full height, and the height is logarithmic base 2 in terms of n. So that is our implementation. Let's try it out to see if we have some mistakes. I think we always have some small typos or anything like this. So let's see if we have some problems here.

Uh, for this, what I'm going to do now is I'm going to actually copy-paste code that I already have. Uh, because the good thing that we can do here is we can actually compare this with the heap in Python. So actually, this was the wrong key here. Now, what I have is I have my min heap and I heapify the following values: 10, 9, 8, 7, 6, 5, 4, 3, 2, 1. I just have the same value as the key, it doesn't really matter. And I then print what happens when I heapify that and I compare that with the `heapq` package or the `heapq` module in Python, which allows me to do the exact same thing. So if I run this now, uh, I can see I get 1, 2, 3, or actually I get 1, 2, 4, 3, 6, 5, 8, 10, 7, 9. Exactly the same result, uh, as the heap package in Python. Only difference is I can also include here a package, uh, so a payload, basically a value. And we can basically do the same thing now with the other methods. So I can compare here what happens when I extract the minimum. I can do the same thing with my heap package here or with the heap module using the `heapq.heappop` method. So I can run this, and we get the same thing: 1, 2, 3. 1, 2, 3. And also I can insert new elements. So I can just, uh, now I need to do this differently. There you go. So I can insert 2 and then print the heap. And there you go. I have, um, Oh, sorry. I saw a mistake here in my parent calculation. It's actually `(index - 1) // 2`, not `+ 1`. This is why my code produced a problem now. So when I try this again, there you go. You can see 2, 4, 5, 6, 9, 10, 8, 7. It's good that we're always testing this because these small mistakes, uh, are often times something that's hard to notice while, uh, writing the code. And, uh, what I can do now as well, this is not something that I can necessarily compare with the `heapq` module, but what I can do is I can also `meld` two heaps. So I can basically say `min_heap2 = MinHeap()` and then I can `meld` them together. And of course, I get a problem. Um, oh, I think I know what the problem is. I am inserting tuples here. They should be lists. No, this is not the problem. `combined_heap = self.heap + other_heap.heap`. Oh, I think that it's `self.heap = other_heap.heap`. There you go. Now it works. And now we have these combined, um, these combined heaps in a single heap. So that is the idea of a heap. Again, this is how you implement a priority queue. You can use this now as a priority queue. You can schedule elements, and then the one with the highest priority, with the lowest value, with the highest rank, you could say, uh, is going to be executed first or extracted first. Um, and of course, you can reverse this. You can make this a max heap by just changing how it works. So you just call this `peek_max`, `extract_max`. And the only difference here is actually that you have to compare, uh, for being greater than and not for being less than. And you have to call this `largest` and not `smallest`. But the idea is the same. You just want to have the largest values at the top. It's just the other way around. But this is how you implement the heap data structure from scratch in Python.

All right. So we're going to implement the Trie data structure from scratch in Python today. And as always, I want to start by giving you guys a brief explanation of the data structure in theory here before we get into the coding. And as a side note for those of you who are interested in that, the data structure name is written like this: T-R-I-E. And it actually comes from the word retrieval, which means that the original correct pronunciation would be "tree." Now, why do we call it Trie? Mainly to distinguish it from the concept of a tree, especially because the Trie is also a tree. It's a tree data structure, which means that if you just say, "Oh, we're working with a tree," we don't really know what we're talking about. Uh, if I say, "I'm working with a tree data structure," so we're calling it Trie mainly to distinguish it from the tree to know it's not just a tree, it's a Trie. That's the only reason why we pronounce it that way. Actually, it would be pronounced "tree" because it comes from the word retrieval. Just as a side note here for those of you interested in that.

Um, but let's take a look at the data structure itself. What's the idea behind it? It's a tree, as we said, and it's very useful for working with strings and primarily used for things like, uh, autocompletion or having a dictionary, for example. Um, and the idea is the following. We have a root node, and every node has two things: a dictionary of children or of child nodes, and, uh, a flag saying if this is the end of a word, yes or no. So we're going to say that if a node is the end of a word, we're going to write "end" in it. Otherwise, I'm going to leave it empty. So this is the root node. Now, it is not the end of a word, and our Trie is empty. Now, let's say I want to insert a word, for example, "hello." How would I do this? Now, what happens here is I go letter by letter and I insert the word into this Trie data structure. So right now, the root node doesn't have any child elements. So what I do is I'm looking for "h." "h" doesn't exist. So I'm going to create a new key-value pair where "h" is the key and "h" points to a node. And this node now has again its own dictionary and can be the end of a word or not. Now, it's not the end of a word. So we're going to continue. Next up, we have "e." "e" is not part of this node or of this dictionary. So we're going to add it. "e" points to the next node, which again has a dictionary. Here we're going to do the same thing. "l" points to the next node, has a dictionary with another "l" pointing to the next node. Um, and this one has a dictionary with "o." And then this "o" points to a node which has an empty dictionary and is the end of a word. This is how we would insert "hello" into our Trie. So we have the root node with the dictionary. The "h" points to a node that has an "e" pointing to a node that has an "l" pointing to a node that has an "l" pointing to a node that has an "o" pointing to a node that right now is empty and has "end" uh, the end flag set to true.

Now, we can also import or insert another word, for example, "minimum" like this, "minimum." Um, and we could see what happens here. Now, there's a reason I choose this word. I'm going to show this here in a second, but let's say, uh, now I'm not going to use the dictionary notation here. I'm just going to use connections, but it's the same idea. The "m" is pointing to a node which is pointing to, uh, which has "i" pointing to another node. "n", "i", "m", "u", "m", and "end." So why am I using this word? Because there are a couple of words that are quite similar. And we're going to see what happens. For example, if I now insert the word "minimal" like this, "minimal." Um, what happens in this case is if I want to insert this word, I go "m", "i", "n", "i", "m", and then I see that here in this dictionary, this, this node here has a dictionary "u" that points to this node. And what I do now is I add another key-value pair. So I say "a" which points now to another node. I'm going to do it like this. So I'm going to just say we have another branch here, "a", which goes to another node, which goes using "l" to another node, which is also the end of a word. And now you can see they have the same prefix. By the way, this data structure here is not just called Trie, it's also called a prefix tree. This is also a way to refer to this data structure, a prefix tree. And the reason for that is you can see "minim" is the prefix for "minimal" and for "minimum," which can be useful again for autocompletion.

Now, another thing that we can do is, let's say I want to insert the word "mini." What happens in this case? Well, in this case, all I have to do is I have to go "m", "i", "n", "i", and then I have to set this to "end." Now, "end" doesn't prevent my Trie from going further. So I can still go to "minimal," but it says that this is the end of a word. It doesn't have to be the end of the search, but it is the end of one word. So "mini" is actually a word. And this can be useful now because if now I ask, "Okay, give me an autocompletion for 'mi'," I can efficiently find "mini," "minimal," and "minimum." And I can extend this. I can build a dictionary like this. I can have, uh, certain keywords like this. This is a very useful data structure. And this is what we're going to implement in Python from scratch today.

So let us get started. I'm going to, or I'm already in my current directory. I'm going to delete everything that's in here. Actually, we don't have anything in here. So I'm going to create a new file. I'm going to call it `trie.py`. And we're going to have, of course, a `Node` class. So `class Node` is going to have a constructor, and it's going to have `self.children = {}`. Um, and `self.is_end_of_word = False` by default. That is our node. That's about it. And then we're going to have a class `Trie`, and this `Trie` is going to have an `__init__` method, and in this `__init__` method, we're going to initialize the root node. So we're going to say `self.root = Node()`. All right. So every tree is going to start with a root node that has an empty child dictionary and is not the end of a word by default.

Now let's define again what kind of methods we're going to implement for this data structure. We're going to have an `insert` method, which is going to allow us to insert a word into the Trie. We're going to have a `search` method, which is going to tell us if a given word is part of the Trie. So, for example, in our tree here, if I type "mini," I'm going to get `True`. If I try, uh, if I type "minimalistic," I'm not going to get a `True`, I'm going to get a `False`. That's the basic idea here. Then we also want to have a `delete` method so that I can remove words. How would I do that in theory? Of course, I would just remove the "end" flag. If I remove "mini," for example, so if I remove "mini," I would just set this to `False` again. Um, if I remove something else, I also delete the nodes and the connections. Uh, we're going to take a look at that, uh, when we get to the implementation. Then we also want to have `has_prefix`. The basic idea here is that we check if the prefix is part of the tree or not. And then we also want to have two a little bit more, not necessarily complicated, but they're going to take more, they're going to have a higher runtime complexity, if that's the correct term, higher. Um, but they're going to be a little bit more difficult, which are going to be the, uh, `starts_with` method. So for this method, we're going to pass a prefix, and this prefix, or this method will give us all the words that start with this prefix. So it's going to search the tree. Um, and then we're going to also have `list_words`, which is basically going to give us all the words of the dictionary, you could say. So we don't need a prefix for this. We just get all the words, and that's basically it. That is going to be our Trie data structure.

Now let us start with the insertion. We already talked about this. How do we insert? We start at the root node. We say `current_node = self.root`. And then what we do is we say, for `char` in `word`: so we go character by character. We say, if the `char` is not part of the dictionary of the `current_node`. So if we don't find the `char` as a key in the `children` dictionary of the `current_node`, what we do is we say, `current_node.children[char] = Node()`. Um, and whether we had to create it or not, afterwards, we're just going to say that the `current_node` is going to be that node. So `current_node = current_node.children[char]`. So either it was there before, then we're just going there, and otherwise, we're creating it and then going there. And we do that until we have no characters left in our word. And then what we do is we say `current_node.is_end_of_word = True`. It's as simple as that. We just follow the path until we get there, or we have to create new nodes until we get there until the word is processed. And at the end, at the node that we're currently at, we're going to just set `is_end_of_word` to `True`. This can be an already existing node, like it was the case for "mini." In this case, we just set it, or it was the node we just created. In this case, we also just set it. Uh, so the insertion is quite simple. We're going to talk about the runtime complexities later on.

The `search` is also quite simple because we have to do basically the same thing, but instead of creating it, if we don't find it, we return `False`. So we say `current_node = self.root`, and then we say, for `char` in `word`: if the `char` is, um, not in `current_node.children`, we're going to return `False` because we obviously don't have it. So if I get to a point where I have a character and it's not part of the children dictionary of my current node, it means the word does not exist, obviously, because the next character does not exist. So I'm going to return `False` in this case. Otherwise, I'm going to keep going down the line. So I'm going to say `current_node = current_node.children[char]`. And in the end, we're going to say, uh, once the word is processed, we want to know the, the word, or the node I'm currently at, is it the end of a word or not. So I'm going to return `current_node.is_end_of_word` because, of course, I can find the term. For example, here, what I could find is, uh, "mini" without the "m." So "mini" "ma," like here, I could end up here, which would be a valid node, but I would not have it set to "end," which means that I would get, uh, `False` here as a return. So that's that.

Now, the rest is going to be a little bit more, um, or actually, `has_prefix` is kind of simple. So for `has_prefix`, we can also do the same thing. Actually, I think we can just copy this. Actually, now I copied it to my diction, uh, to my to my clipboard. So, let's go paste it down here. Uh, the only difference here is that we're going to return `True` every time. So it doesn't need to be the end of the word because we're not checking if the word exists. We're checking if the prefix exists. So if I end up at a node, I can return `True`.

Now, the `delete` will be a little bit more complicated, um, because we need to define a helper function `_delete`. We're going to say `def _delete(self, node, word, index)` and this function will get parameters so that we can keep track of certain things. First of all, it will get the `current_node`, it will get the `word`, and it will get the `index` so that we can recursively call it and update the progress, so to say. Um, the idea is I'm going to call this function or this method in `delete` once initially. So `self._delete(self.root, word, 0)`. So I'm going to say `self.root`, this is the word that needs to be deleted, and I'm currently at index zero. So we haven't processed anything of the word yet. And in our `delete` method, this is going to be a recursive method. So it's going to call itself. We're going to have, um, first of all, some base cases for terminating. We're going to say, if the `index == len(word)`, then we're done. And I basically just have to see, is this, uh, the end of a word? So if not, if `current_node.is_end_of_word` is `False`, we return `False`. Why do we return `False`? Because we don't need to do anything. We don't need to delete anything. This happens when the word didn't exist anyway. So we don't need to delete anything, uh, on the upper levels. We can just say, okay, if I'm ending up at a place that is not a word, I don't even have to do anything. So return `False`. Uh, the return value is important because we have to also recursively remove nodes if, uh, if it's necessary. So basically, if I'm removing this here, I just need to set it to not `is_end_of_word` anymore. So if I'm removing "mini," if I'm removing "minimal," I have to remove this. I have to remove this, and also this connection here. So I have to remove more than just, uh, setting this to not being an "end" anymore, unless I want to keep like this or not, not even unless I want to keep the structure, I have to delete it because otherwise "minimal" would be a valid prefix, which it shouldn't be. So this is why I use the return values here. So if I end up at a place that is not the word, I just return `False` because obviously I'm not removing anything here. Um, and then I'm going to say `current_node.is_end_of_word = False`. Now, if it was `False` already, this doesn't change anything. If it was `True`, it means that I'm ending up at a place where this is a word. This is the end of a word, and it is set to `True`. So I'm going to set it to `False` now to say this is no longer a word. I'm removing it from the dictionary, so to say, from the Trie. Um, and then I want to return `len(current_node.children) == 0`. If that is the case, I want to return `True`. So if, if I don't have any child nodes at the current node, I can return `True` because that means that I can delete, uh, other nodes as well. Whereas if this has child nodes, I cannot just delete everything because there are other words that would be impacted by it. So I return `True`, which means you can delete the node, um, if this node doesn't contain any child nodes. Um, so that's the base case. Otherwise, what we're going to do, or not just otherwise, or actually otherwise, yeah, because, uh, we return if we get into the `if` statement. Uh, otherwise, what we're going to do is we're going to say, `char = word[index]`. Remember, we're passing the index here, uh, or we're going to pass the index here recursively when we call the `delete` method, but by default, or in the beginning, it's zero. So we're getting the first character, uh, or the character at the index. And then we say `next_node = current_node.children.get(char)`. So from the `current_node`, I'm looking at the child dictionary. I'm getting the node, uh, that corresponds to the key `char`. Now, there is the case that this node does not exist. So if, or this key does not exist. If this is the case, this is going to return `None`, and I can return `False` because the word doesn't exist. If the word does exist, uh, what I do is I delete the current node. How do I do that? Or I, I don't delete the current node. I call recursively the `delete` function, but I have to store whether I have to delete the current node or not in a variable. So this is why we need to return values. So we say `should_delete_child = self._delete(next_node, word, index + 1)`. What this means is we go one node forward and we also increase the index by one so that we can continue the same process down the line. And this is going to recursively return `True` or `False`. And if it returns `True`, it means that I can delete the current node. If it returns `False`, it means that I'm not going to delete the current node. So at some point, this is going to return finally. And then I want to know if `should_delete_child`: what I'm going to do is I'm going to `del current_node.children[char]`. And I'm going to return also here, uh, for this node, if `len(current_node.children) == 0` and also `not current_node.is_end_of_word`. So basically, I get the instruction, delete this node, and then I delete this node from, from the children, and I also say for this node, delete it if it has no children or if, and if it's not the end of a word, so that we can recursively delete all the nodes that are no longer necessary in our Trie. I hope this was not too confusing in the explanation. The basic idea here visually again, let me show this, is for some nodes, when you, when you want to delete the word like "mini," all you have to do is you have to delete the flag that it's the end of a word. You don't have to remove any other references here because it has child nodes. But for example, if I remove "minimal," this doesn't have child nodes, so I can remove this node. I can remove, of course, the flag, I can remove that this is the end of a word, but I also don't have children, which means I can remove this node, which means I can remove this node because it then also doesn't have any children anymore, uh, which means that, um, this connection can also be removed. But then, of course, this should not be removed because it does have children, it does have "minimum" in other words that is also part of our Trie. So I hope this is somewhat easy to understand here why we're doing it that way, even though the recursion might be confusing, but we're basically returning, "Should you delete me or should you not delete me?" That's the return value. All right. So that's the `delete` method.

And now for the `starts_with` and for the `list_words` method, we're going to use a depth-first search. So a DFS algorithm. The basic idea is you want to go to a certain prefix, and then you want to get all the child words. So not just the nodes, but the words. You want to explore all the child nodes to find words, and you want to collect them in a list. So we're going to say `words = []`. And we start again at the root node. Then we say, for `char` in `prefix`: so we want to go to the position, and we want to say, if `char` not in `current_node.children`, we're going to return an empty list, or actually, we can return `words` because it's going to be an empty list at this point. Um, but if we don't get into this `if` statement, we're going to just go further and further. We're going to say `current_node = current_node.children[char]`. Which means we're going to go to the prefix. For example, if my prefix is "m," or if my prefix is "mini," or let's say "min," I would go to this point here, "min." This is where I'm at now. And from here, I can start a DFS. So I can go like this, and then like this. So a depth-first search. Um, all right. So once this is done, we're going to be at the position of the last prefix character. And then we're going to define here a helper method, which is going to be, it's going to be a nested method inside of this, uh, `starts_with` method. And I'm going to say `_dfs(self, node, path)` is going to get a `current_node` and a `path`. The `path` is important to be able to reconstruct the word. And this is going to recursively call itself. So we have quite a bit of recursion today. Uh, basically, the idea is if the `current_node.is_end_of_word` is `True`, we want to store it. We want to add it to our `words` list here. So if we end up at a node that is the end of a word, what we want to do is we want to say, `words.append("".join(path))`. And the `path` is going to be a collection of characters. Um, so in order to get it as a word, we need to join it. So we're going to say `"".join(path)`. So the `path` is going to be what we recursively pass here to the function call. So if we are at the end of the word, get all the characters, join them together, and append them to the `words` list. Uh, and then we're going to say, for `char, child_node` in `current_node.children.items()`: So basically, for the key and child node, `char` being

The character that performs the transition, child node being the node that the transition is performed to. Uh, we're going to say DFS go to that child node and say path plus and then list C. This is important that it's a list because we're extending an existing list. So this is the list of characters that we have. We collect all the characters and at the moment we arrive or the moment we arrive at um at the end of a word, we collect it. And of course, we need to call this method once. We need to say DFS current node here and we start with a prefix. This is important because you want to not start with an empty list. You already have the beginning. For example, min is already part of the word, so you want to append to it. Um, in our example, I can show you that uh what we want to do here is we want to go to this position to min and then what we want to do is we want to do the DFS. So we want to go down. Oh, here's the end of a word. So what I do is I have now m i n e, uh m i n i and I want to join them together to many and collect them in my list of words. Then I go deeper. I say m, then I say a l o, end of word. Perfect. So I can say now um I have m a l, join them together, minimal, and then I also have here a second call, of course, u m o n of the word. Okay, this is minimum. So I found all the words that have this prefix that start with min. Um, and of course, what I need to do in the end is I need to return the list of words. All right. Now, list words is basically a similar approach. Only difference being we don't need a prefix. So what we do here is we say words is equal to an empty list and we say again DFS. We're going to have a current node and a path. Actually, I think this is the exact same implementation. So, I'm going to just copy this and we're going to say that um the only difference is that we're calling this DFS now on self.root with an empty list as the prefix and then we say return words. That's it.

Now, if I didn't make any mistakes, which would be surprising as always, um, that is the tri data structure. So I'm going to write some uh test cases here just to see if this works and then we're going to talk about the runtime complexity. So if name is equal to main, what I want to do is I want to create a tri. And actually, let me think about this. I'm going to just copy paste what I have here in my prepared code so that we don't have to actually. This was not the correct key. Let me just do it like this. This. There you go. And uh, what we do here is we have basically a tri. We insert hello, Henry, Mike, minimal, minimum. Let's also insert many. And um, then we have or actually, I'm inserting many down here. So let's remove it here. Uh, let's run this code to see if it works. No, it doesn't work. Key error H. Perfect. This means that our insert method probably doesn't work correctly. So, what's the problem here? Oh, I found the problem. It's that we're missing a knot here. Of course, you want to create a new node if it's not in the children. You otherwise want to just go to the node. But if you don't have the character already in the list, then you want to create a new one. Otherwise, just jump to the existing one. That's a problem. Um, we have another problem, which is name W is not defined. So where is that again? This is in has prefix. Oh, is this because we're lacking a parameter? No, actually has prefix is fine, but we need to say prefix. And now it should work. Okay, let's compare the code or let's compare what it should do. We insert hello, Henry, Mike, minimal, minimum. We can print that. We get it. Um, this is from list words. So this works. Then we say has prefix. Actually, what we're asking for here is MI. It has it. Um, if I say starts with MI, I get mike, minimal, minimum. If I say um delete minimal and then I do starts with MI again, I get Mike and minimum. Then I search for certain words. I search for minimum, minimal, and mini. I get uh in this case true, false, false because I removed minimum and then we insert uh or I removed minimal. Then we insert mini and then I say starts with MI and I'm getting mike, mini, and minimum. So as you can see, this works. And now let's talk about the runtime complexity. How difficult is it to do that? Well, for the insert, we have O of M, so linear runtime complexity where M is the length of the key. So actually the length of the word we could say. So depending on how long the word is that we're inserting, that's what determines the runtime complexity. It doesn't matter how large the tree is. It doesn't matter um, you know, how many words are already in there. It matters how long the new word is that I'm trying to insert. O of M where M is the length of the word. So it's linear in terms of word length. Um, when it comes to the search, it is basically the same O of M. O of M. Actually, let me just copy that because what do we need to do? We need to just go and look up the characters and go to the next node and next node, next node. Now, of course, we can terminate earlier. If we see that the first letter is already not part of the tri, then we can of course just terminate. But in the worst case, we have O of M, which is the length of the word itself. So then the same is also true for deletion O of M. In this case, actually, I wanted to paste this here again. Um, and for has prefix, we also have O of M. But for the other ones, uh, for the starts with and for list words, we have different runtime complexities. For starts with, we have the following. We have O of M plus K, where M is the prefix length and K is the total number of characters in all suffixes. Basic idea being, I definitely have to go M because I have to go to the node where the prefix ends. So that's for sure. And then I have to go to all the characters um and all the suffixes. So for example, in our tree, in in our tri here, we definitely have to go to min. But then I also have to go to I M A L M U M. Now, the thing is, if they overlap, I can save certain things. So for example, if my prefix is M, then I N I and M overlap. So I only have to count them once. So I don't actually have to count uh all the words lengths because then I would have I N I, which would be three. I would have I N I M A L, which would be all of that. And then I would add all these together. If I have overlaps, this results in much less characters that I have to count because if they only differ in the last couple of characters and I have huge words, that's going to make a difference. But in the worst case, I have um O of M plus K, where M is the prefix length. That's how far I have to go for sure. And then K depends on the overlaps, but K would be the total number of characters in all suffixes. Um, and then we have also list words, which is easy to to denote. It's just O of N. But N is the number of nodes in the tri. We have to go through every single node uh in order to list all the words. So depending on how many nodes you have in the tri, that's how many nodes you have to traverse in order to list all the words. So yeah, this is how you implement the tri data structure in Python from scratch.

All right. So, we're going to implement the graph data structure from scratch in Python today. And I think most of you guys will probably already know what a graph is. Nevertheless, I want to give you a brief theoretical explanation just so we know what we're talking about. Um, a graph basically consists of a bunch of nodes and a bunch of edges. So, we have nodes like these here. Usually, they have some label assigned to them like ABC or 1 2 3, uh, and so on. So let's call them 1 2 3 4 5 6 7 8 9. And these nodes can be connected by edges. So one and two might have an edge. Two and three might have an edge. Three and four, five and six, seven and six. Maybe also three and six. Maybe eight and six. Six and nine. Eight and nine. Five and eight. Four and seven. Four and three, four and six, uh, maybe also one and five and also one and four, whatever. Um, that would be a graph. And also, one thing that you might notice is that a tree is also a graph with a specific limitation that there are no cycles. So, for example, if I have uh something like this A, B, C, and then maybe D. It doesn't have to be a binary tree. It can also be something like this. This is a graph, but this is also a tree. But the moment I create a cycle like this, it's no longer a tree, but it's still a graph. Um, and what we're seeing here is an undirected graph. So it means that the connections go both ways. One is connected to two, two is connected to one. And um, unless I specify that I want to have a directed graph, every connection goes both ways. Now, in a directed graph, every connection needs to have a direction. So one goes to two, for example, but two doesn't go necessarily to one. If I also want to have two go to one, I need to add a second connection uh from two to one. So that's possible, but then I need two connections. And every single connection has to have a direction. So we cannot have uh undirected indirected connections in the same graph. It's either an undirected graph um or a directed graph. So that's the basic idea here. And also, we can have weighted graphs. So it doesn't have to be just directed undirected. Both can also be weighted graphs, which means that each connection has a certain weight to it. This can be a cost. This can be uh a speed. This can be uh a reward or something like this, depending on what you're trying to model. But for example, one question could be, what's the fastest road from or the fastest path, the shortest path from one to five, for example? And if this connection here doesn't have a weight, if none of the connections have weights, then of course that's the shortest path. I just have to hop once. But if I assign weights to the connections like costs to the connections or uh slowdowns, I could say that this has a cost of 100 and maybe I could say this one has a cost of 50 and this one has a cost of 10 and then this one has a cost of 10 as well. Then this path already would be faster because it only costs 70 or cheaper, whatever you want to call it. But then maybe I have connections like these, one, one, one, then of course that's the cheapest path possible, even though I have to go through a lot of nodes, but if they're all cheap paths, I can just go like this and that's the fastest or cheapest way to five. So depending on whether we're working with um with weighted or not weighted graphs, this changes what we're looking for. Um, now graphs are very versatile. They have a lot of different use cases. They're used all over the place for network analysis, for um, for also graph neural networks, and a lot of different things can be done with graphs. But in this video today, I don't want to show you every single thing that you can do with graphs. I just want to provide a basic implementation, adding nodes, removing nodes, uh, adding edges, removing edges, and I want to also show you some basic stuff like DFS and BFS. So BFS stands for breadth uh first search. We're going to talk about this in more detail when we get to the implementation. And DFS, which is depth first search. These are two things that I want to show you. Then I'm also going to provide you with a code for uh Dijkstra. I want to also provide you with a code for transforming or yeah, transforming the adjacency list to an to an adjacency matrix. And I also want to provide you with code for uh the shortest path algorithm. But I'm not going to explain them. So I'm just going to copy paste them. I'm going to upload them to GitHub. But these two here, I'm going to actually implement with you guys in the video. I just don't want to make this video too comprehensive because we could implement a ton of things when it comes to graphs. I want to give you a basic implementation and then you can take it from there and extend the functionality if you want to. So that's what a graph is, basically. Um, so let's get into the coding. We're going to open up a new Python file here. I'm going to call it graph.py. And this time, we're only going to have the graph class. We're not going to have any uh node class here. Even though we're going to have a bunch of nodes, but they're going to be represented as an adjacency list. Maybe that's one thing that I want to show you as well, also here in the in the theoretical part. An adjacency list is basically how you can represent uh a graph. So, for example, uh this graph could be represented the following way. I would have the adjacency listed. One has a connection to two, four, and five. And then two would have a connection to one and three. And then uh three would have a connection to uh two, four, five, six, like this. That would be an adjacency list. Adjency. Come on. Adjacency list. We can also have an adjacency matrix. Uh, which makes more sense or can be more interesting when we have directed graphs. But basically an adjacency matrix, the idea here is that I have all the nodes 1 2 3 and so on. Uh, 1 2 3 and so on. And I basically say, do I have a connection from one to two? If I have one, yes. Do I have one from one to three? Uh, if I have none, zero. And I fill this up uh with ones and zeros. So that's just a different way to represent this. We're going to work with the adjacency list. And we're going to start now by saying class graph and we're going to define the init method. We're going to pass the argument directed. By default, this is going to be false. So it's going to be an undirected graph by default. And we're going to set directed equal to directed. Also, we want to initialize an empty adjacency list. So, we want to say self.adjacency list is equal to dictionary to an empty dictionary. And then we want to define all the methods that we're going to implement. Now, we're going to need a representation dunder. So, wrapper self. This is just going to print the adjacency list. We're going to have an add node function. or method. We're going to pass a node that is going to be added to the graph. We're going to have add or actually remove node as well. We're going to have um add edge, which is going to take as parameters from node, to node, and weight. By default, weight is going to be none. This is going to allow for weighted connections, which are optional. You can also have not weighted connections. Uh, we're going to have remove edge, which is going to also take from node and to node as parameters. Then we're going to have get neighbors for a given node. Also not too difficult to implement. We're going to have has nodes, which is also going to be very simple and straightforward. Uh, we're going to have also has edge from node to node. Then we're going to have get nodes and we're going to have get edges. Um, now besides that, we're going to have the two functions or methods that I talked about, which are the BFS and the DFS. So we're going to say BFS self um starting from a specific node from a start node, and also the same for the DFS. All right. So these are the methods that we're going to implement in this video today. And I want to start right away with the representation dunder. All we're going to do here is we're going to create a graph string and it's going to be an empty string in the beginning and then we're going to iterate over the pairs in the adjacency list and we're just going to display them with simple arrows. So we're going to say here for um for node and neighbors in adjacency list self.adjacency adjacency list. Actually, um we're going to just do the following to the graph string. We're going to add the following an F string which is going to be the node and an arrow pointing to all the neighbors and then also backslash n so that we have a new line and then we're going to return that. So that's basically the graph string. Now, adding a node is also quite easy. We're going to just say if the node not in adjacency list dot um keys or actually we don't need to do keys. We can just do it like this. If it's not already in the adjacency list, we're going to say self.adjacency list node is going to be equal to an empty set. So we don't have any neighbors yet. We just added node. Otherwise, we're going to raise a value error. We're going to say node exists already or you can just do nothing. Depends on what you want to do. Um, so that's that. Now, removing a node is also quite simple. If the node is not in self.adjacency list, then we're going to say raise value error node does not exist. So you're trying to remove something that does not exist. Otherwise, for every neighbor in self.adjacency list dot values, remove that node. So, we're going to say for every set of neighbors, if this node occurs there, remove it from there because it no longer exists. So, we're going to say neighbors.card note. Uh, and then we're going to of course also say delete from the adjacency list this node entry. All right. So that's that. For adding an edge, we have to consider that we could have a weighted connection or we could have a not weighted connection. So we're going to say uh first of all, from node, if the from node is not in self.adjacency adjacency list. What we want to do is we want to create it. So we want to allow for edges to be created for nodes that don't exist yet. Not because this is possible, but because we're just going to add the nodes on demand. So we're going to say here if from node is not in self.adjacency list. We want to say self.add_node(from_node). This just makes it easier. We don't have to create the nodes manually and then the connections. We can just say add the connection from one to two and if both don't exist, we're going to create them. So we're going to do it like this. I'm going to copy that. We're going to do the same thing for the two node and then we're going to say if weight is none. So if we don't have a weight, we're going to just say self.adjacency adjacency list um to node is going to be or actually from node first, from node, um to node, and then we're going to say if this is a directed graph, we want to have it only in one direction, otherwise, so if this is not a directed, so if self.directed or actually if not self.directed, we also want to do it the other way around. adjacency list to node at from node. So then it goes both ways. A connection between one and two is also a connection between two and one if it's not a directed graph. And otherwise, if it is a weighted graph, we don't want to just append the node. We also want to append the weight. So we actually want to take this, copy it, paste it down here. And the only difference is that now we add a tuple and the tuple is going to be two node, weight, and it's going to be now I pressed the wrong key, it's going to be from node, weight, and that should be it. So that's how we add an edge and then we're going to also remove an edge. How do we do that? Well, if from node is in self.adjacency adjacency list um and if to node is in self.adjacency adjacency list from node. So if the node exists in the list and if actually the two node is a connection is a neighbor of from node, then we're going to just say self.adjacency adjacency list and then from node, from here, we want to remove the two node's entry actually parenthesis, so that is a case where everything exists and everything is fine. Otherwise, we want to say here again, raise a value error. Um, actually, I just called this remove, it's remove_edge. So this will be just edge does not exist. The edge we're trying to remove does not exist. Otherwise, here we can even say node does not exist. So raise value error. Uh, or actually, let's just say edge does not exist. It's simpler. I don't want to explain all the details of why it didn't work. But inside of here, we also want to do something else. We want to say if not self.directed, we also want to do it the other way around. So if I remove an edge, I have to remove it from both entries unless it is a uh directed graph. So I'm going to say here if uh from node in self.adjacency list to node, if that's the case, self.adjacency adjacency list to node remove from node. All right. So that's the removal of the edge. The other functions here now, except for BFS and DFS, are very easy to understand. Uh, get neighbors obviously, all we have to do is we have to return self.adjacency list. um adjacency list and then get the specific node. In the default case, just return an empty set. That's it. Get all the neighbors. Empty set by default if it doesn't exist. Um, has node is also quite simple. Return node in self.adjacency list. That's all we need to do for this. Has edge is also just return or actually we need to to say if from node in self.adjacency adjacency list. Then we just say return two nodes um in self.adjacency list from node. So is it part of it or not? This is going to return a boolean and otherwise we return false. Anyways, get nodes is also not too difficult. Just return a list of self.adjacency list dot keys and the edges are actually just a simple loop or actually two loops. We're going to say edges is an empty list for from node, neighbors in self.adjacency list dot items. So we iterate over the items in the adjacency list and then we say for two node in neighbors, edges append and then from node, to node. So this is all very simple. Now, the I wouldn't say difficulty, but the interesting stuff happens now in BFS and DFS. So what's interesting about these two functions or these two algorithms is that we're going to use data structures that we've already talked about in this tutorial series. We're going to use a queue for the BFS and we're going to use a stack for the DFS because of the different order or the different processing order. In a queue, it's uh first in first out FIFO, and in a stack, it's last in first out, and because of that, we have uh these as helping data structures here. In this case, we're just going to use lists and we're going to pop the elements in different ways, but these are basically queues and stacks. So, we're going to say here for the BFS, we want to have a set of visited nodes and we want to have also a queue of nodes to be processed. We are going to start with a single node in here and then we're going to have our resulting order, which is going to be the traversal order. And what I want to do here is I want to say while we still have elements in the queue, we want to get the next element to be processed in the first in first out way. So we're going to say here that um the node is going to be Q.pop at index zero to get the first element. The first element was added to the queue. And then we're going to say if this node uh is not already in visited, so it's not already processed, we're going to go further. So we're going to say first of all, add it to the visited nodes and then also append it to the order. So to our resulting list and then I want to get all the neighbors of this node. So in the beginning, all the neighbors of the starting node. So we're going to say neighbors is equal to self.adjacency list and um we're actually, we can use, we have a function for this right, get neighbors. So we're actually going to use the get neighbors function, self.get_neighbors for this node. And what we want to do now is we want to iterate over them. We're going to say for neighbor in neighbors, if is instance neighbor tuple, which means that um it's a weighted connection because we have a weight. We don't just have the individual value, but we have also the weight. Uh, what we're interested in then is just the value because we don't care about the weight. Now, we're just going to say neighbor zero. Otherwise, we're just going to take the neighbor itself and we're going to say Q dot or actually sorry, not otherwise, we need to do this uh in all cases. The only case in which we don't do that is if we have already visited that neighbor. So if neighbor is not in visited, we're going to append it to the queue. So we take a look at all the neighbors that we have. Have we already processed them? Have we already visited them? If not, put them to the queue and process them further again in this first in first out principle. And in the end, this is going to result in the BFS traversal order because we're taking in the neighbors and since they're the first elements to be added, they're also the first elements to be processed, which is the BFS approach of going layer by layer. In the DFS, we're going to do all of that the opposite way. We're going to do that with a stack. And um we're going to change Q to stack. And besides that, uh I think the only thing we're going to change is of course, we're going to do pop without an index. So it's going to be the last element. And we're also going to um to sort the neighbors. So we're going to say for neighbor in sorted neighbors. And we're going to reverse the order. Now, I think that's not necessary, but that's usually what you do. So, just uh reverse the order of of the neighbors when you when you list them. But besides that, this is actually the same. The only difference is I'm going uh last in first out. So, whatever enters first is processed last, which is the depth first approach. This is why we use a queue and a stack. So before we go to the other functions that I have here, or actually, I'm going to go through the other functions. Um, I'm actually just going to add them here to show them to you. The reason I add them is because they have functionality that uh interacts with the weights, but I'm not going to implement it. I'm not going to explain it here. I'm going to provide the code to the GitHub uh repository or in the GitHub repository uh for this tutorial series. But um, if you are interested, for example, in the explanation of Dijkstra, I have a video for this or on this on this channel uh in my algorithms and data structures tutorial series. You can take a look at the theory there. But this is the implementation here. It uses a heap. And we also have shortest path here. And also, I want to use a method called to adjacency matrix, which is going to allow us to turn our adjacency list into an adjacency matrix. So I'm going to also paste this here. Actually, this needs to be one level before. So again, these are not going to be explained. I'm just going to paste them here and you can copy paste them from the repository. But now we want to see if our graph actually works. And for this, I'm also going to copy paste the examples here. So I already have the main section. Basically, we create a graph A B C D E F G. Actually, this is not even necessary because we can just create the edges. And then I'm trying to find the shortest path from A to C. Now, just so we know what we're talking about here, let's actually try to um recreate this graph visually. So what does this graph look like? We have a uh this is a weighted graph right now. We have a points to b, a points to c. B points to to c as well. So here we have a cost of one. Here we have a cost of 10. Here we have a cost of one. Then we have B going to D, D going to C as well. All with a cost of one. We have A going to E. We have E going to F. We have uh G going to F. I think this is an undirected graph, so it doesn't really matter. We have F going to H and we have H going to I and we have I going to G, which is now this. And this one has a connection of 100 or a cost of 100, and all these have one. So that is our graph and we're asking the following: BFS from A, DFS from A, Dijkstra from A, and then shortest path from A to C. Let's run this. Okay, I'm calling this method uh edge and not edge. So add um and also I have a problem here. I need to actually iterate over the items of the adjacency list, not over the adjacency list keys. So that should be it. Let's run this. And we also have a problem. Did you mean note this is 86 in BFS? So let's go 86 in BFS. Yeah, actually, of course, note notes also here, note note R have some typos in here. Uh, and Q is not defined obviously because we're working with a stack here. So stack.append pend. But besides that um we also have it uh we also have it here of course stack stack and that's it. Okay. So let's take a look at that. Uh, what do we have here? We asked for what did we ask for? We asked for the adjacency matrix, which is what we get here with the connection weights. We asked for the BFS from A. So we get A E C, which makes sense. A. So A E C B because these are the neighbors. Then we get F D, which are the neighbors of the neighbors. Uh, and then we get the rest, which is um H I G. In case of DFS, we get A B C D E. So A B C D. Okay. Then it goes to the next neighbor E and then we get to F and then it goes H I G. Uh, also makes sense. Then the Dijkstra is in order to get from uh A to A, we need zero cost. In order to get from A to B, we need one cost. In order to get from A to C, we need a cost of two. In order to go from A to D, we need a cost of two, and so on. So you can just see the cost for every shortest path. And then the shortest path from A to C is A B C, which is of course true because ABC has a cost of two, and AC would have a cost of 10. Um, all right. So this is how you can implement the graph data structure from scratch in Python.