So, in this video, we'll go over the basics behind implementing binary search trees. We are not going to focus on the balance aspect in this video that will be discussed in later videos and we are going to talk about things which are true for binary search trees on general, balanced or otherwise. But let's just recall, you know, why are we doing this, you know, what is the raison d'être of this data structure, the balance version of the binary search tree and basically, its a dynamic version of a sorted array. So, that's pretty much everything you can do on a sorted array, maybe in slightly more expensive time. They are still really fast but in addition to this dynamic, it accommodates insertions and deletions. So, remember, if you want to keep a sorted array data structure, every time you insert, every time you delete, you're probably going to wind up paying a linear factor which is way too expensive in most applications. By contrast with the search tree, a balanced version, you can insert and delete a logarithmic time in the number of keys in the tree. And moreover, you can do stuff like search in logarithmic time, no more expensive than binary search on a sorted array and also you can sort of say the selection problem in the special cases, the minimum or maximum. Okay, it's not constant time like in a sorted array but still logarithmic pretty good and in addition, you can print out all of the keys from smallest to largest and in linear time, constant time per element just like you could with the linear scan through a sorted array. So, that's what they're good for. Everything a sorted array can do more or less plus insertions and deletions everything in logarithmic time. So, how are search trees organized? And again, what I'm going to say in the rest of this video is true both for balanced and unbalanced search trees. We're going to worry about the balancing aspect in the later videos. Alright, so, let me tell you the key ingredients in a binary search tree. Let me also just draw a simple cartoon example in the upper right part of the slide. So, this one to one correspondence between nodes of the tree and keys that are being stored. And as usual in our data structure discussions we're going to act as if the only thing that we care about, the only thing that exists at each node is this key when generally, this associated data that you really care about. So, each node in the tree will generally contain both the key plus a pointer to some data structure that has more information. Maybe the key is the employee ID number, and then there's a pointer to lots of other information about that employee. Now, in addition to the nodes, you have to have links amongst the nodes and there's a lot of different ways to do the exact implementation of the pointers that connect the node of the tree together but the video I'm just going to keep is straightforward as possible and we're just going to assume that in each node, there's three pointers. One to a left child, another one to the right child and then the third pointer which points to the parent. Now, of course, some of these pointers can be null and in fact in the five node binary search tree I've drawn on the right for each of the five nodes, at least one of these three pointers is null. So, for example, for the node with key one it has a null left child pointer, there was no left child. It's the right child pointer going to point to the node with key two and the parent pointer was going to a node that has key three. Similarly three is going to have a null parent pointer and the root node in this case, three is a unique node but has a null parent pointer. Here the node with key value three, of course, has a left child pointer points to one and has a right child pointer that points to five. Now, here is the most fundamental property of search trees. Let's just go ahead and call it the Search Tree Property. So, the search tree property asserts the following condition at every single node of the search tree. If the node has some key value then all of the keys stored in the left subtree should be less than that key. And similarly, all of the keys stored in the right subtree should be bigger than that key. So, if we have some node who's stored key value is x and this is somewhere, you know, say deep in the middle of the tree so upward we think of as being toward the root. And then if we think about all the nodes that are reachable, after following the left child pointer from x, that's the left subtree. And similarly, the right subtree being everything reachable via the right child pointer from x, it should be the case that all keys in the left subtree are less than x and all keys in the right subtree are bigger than x. And again, I want to emphasize this property holds not just to the root but at every single node in the tree. I've defined the search to a property assuming that all of the keys are distinct, that's why I wrote strictly less than in the left sub tree and strictly bigger than in the right subtree. But search trees can easily accommodate duplicate keys as well. We just have to have some convention about how you handle ties. So, for example, you could say that everything in the left subtree is less than or equal to the key at that node and then everything in the right subtree should be strictly bigger than that node. That works fine as well. So, if this is the first time you've ever heard of the search tree property, maybe at first blush it seems a little arbitrary. It seems like I pulled it out of thin air but actually, you would have reversed engineer this property if you sat down and thought about what property would make search really easy in a data structure. The point is, the search tree property tells you exactly where to look for some given key. So, looking ahead a little bit, stealing my fire from a slide to come, suppose you were looking for say, a key 23, and you started the root and the root is seventeen. The point of the search tree property is you know where 23 has to be. If the root is seventeen, you're looking to 23, if it's in the tree, no way is it in the left subtree, it's got to be in the right subtree. So, you can just follow the right child pointer and forget about the left subtree for the rest of the search. This is very much in the spirit of binary search where you start in the middle of the array and again, you compare what you're looking for to what's in the middle and either way, you can recurse on one of the two sides forgetting forevermore about the other half of the array and that's exactly the point of the search tree property. We're going to have to search from root on down, the search tree property guarantees we have a unique direction to go next and we never have to worry about any of the stuff that we don't see. We can also draw a very loose analogy with our discussion of heaps and may recall heaps were also logically, we thought of them as a tree even though they are implemented as an array. And heaps have some heap property and if you go back to review the heap property, you'll find that this is not the same thing as the search three property. These are two different properties and that's going to trying to make different things easy. Back when we talk about heaps, the property was that this is for the extract min version. Parents always have to be smaller than their children. That's different than the search tree property which says stuff to the left, that's smaller than you, stuff to the right is bigger than you. And heaps, we have the heap property so that identifying the minimum value was trivial. It was guaranteed to be at the root. Heaps are designed so that you can find the minimum easily. Search trees are, are defined so that you can search easily that's why, you have this different search tree property. If you want to get smaller, you go left. If you want to get bigger you go right. One point that's important to understand early, and this will be particularly relevant once we did, once we try to enforce balancing in our subsequent videos is that, for a given set of keys, you can have a lot of different search trees. On the previous slide , I drew one search tree containing the key values one, two, three, four, five. Let me redraw that exact same search tree here. If you stare to this tree a little while you'll agree that in fact that every single node of this tree, all of the things in the left subtree are smaller, all of the things in the right subtree are bigger. However, let me show you another valid binary search tree with the exact same sets of keys. So, in the second search three, the root is five, the maximum value. And everybody has no right children, only the left children are populated and that goes five, four, three, two, one in descending order. If you check here again, it has the property that at every node, everything in the left subtree is smaller. Everything in the right subtree, in this case, empty, is bigger. So, extrapolating from these two cartoon examples, we surmised that for a given set of n keys, search trees that contain these keys could vary in height anywhere from the best case scenario of a perfectly balance binary tree which just going to have logarithmic height to the worst case of one of these link list like chain which is going to be linear in the number of keys n. And so just to remind you the height of a search tree which is also sometimes called the depth is just the longest number of hops it ever take to get to from a root to a leaf. So, in the first search tree, here the height is two and then the second search tree, the height is four. If the search tree is perfectly arranged with the number of nodes essentially doubling at every level, then the depth is you're going to run out of nodes around the depth of log2n. And in general, if you have a chain of n keys that that's going to be n - 1 but we'll just call it n amongst friends. So, now that we understand the basic structure of binary search trees, we can actually talk about how to implement all of the operations that they support. So, as we go through most of the supported operations one at a time, I'm just going to give you a really high level description. It should be enough for you to code up on implementation if you want or as usual, if you want more details or actual working code, you can check on the web or in one of the number of good programming or algorithms textbooks. So, let's start with really the primary operation which is search. Searching, we've really already discussed how it's done when we discuss the search tree property. Again, the search tree property makes it obvious how to look for something in a search tree. Pretty much you just follow your nose you have no other choice. So, you started the root, it's the obvious place to start. If you're lucky, the root is what you are looking for and then you stop and then you return to root. More likely, the root is either bigger than or less than the key that you're looking for. Now, if the key is smaller, the key you are looking for is smaller than the key of the root, where you're going to look? Well, the search tree property says, if it's in the tree, it's got to be in the left subtree so you follow the left sub child pointer. If the key you're looking for is bigger than the key at the root, where is it got to be? Got to be in the right subtree. So, you're just going to recurse on the right subtree. So, in this example, if you're searching for, say the key two, obviously you're going to go left from the root. If you're searching for the key four, obviously you're going to go right from the root. So, how can the search terminate? Well, it can terminate in one of two ways. First of all, you might find what you're looking for so in this example, if you search for four, you're going to traverse to right child pointer then a left child pointer and then boom, you're at the four and you return successfully. The other way the search can terminate is with a null pointer. So, in this example, suppose you were looking for a node with key six, what would happen? Well, you start at the root, three is too small so you go to the right. You get to five, five is still too small cuz you're looking for six so you try to go right but the right child pointer is null. And that means six is not in the tree. If there was anywhere in the tree, it had to be to the right of the three, it had to be to the right of the five but you tried it and you ran on the pointers so the six isn't there. And you return correctly with an unsuccessful search. Next, let's discuss the insert operation which really is just a simple piggy backing on the search that we just described. So, for simplicity the first think about the case where there are no duplicate keys. The first thing to do on this insertion is search for the key k. Now, because there are no duplicates, this search will not succeed. This key k is not yet in the tree. So, for example, in the picture on the right, we might think about trying to insert the key six. What's going to happen when we search for six, we follow a right child pointer. We go from three to five and then we try to spot another one and make it stuck. There's a null pointer going to the right of five. Then when this unsuccessful search terminates at a null pointer, we just rewire that pointer to point to a node with this new key k. So, if you want to permit duplicates from the data structure, you got to tweak the code and insert a little bit but really barely at all. You just need some convention for handling the case when you do in counter the key that we are about to insert. So, for example, if the current note has the key equal to the one you're inserting, you could have the convention that you always continue on the left subtree and then you continue the search as usual again, eventually terminating at a null pointer and you stick the new inserted node you rewire to null pointer to point to it. One good exercise for you to think through which I'm not going to say more about here is that when you insert a new node, you retain the search tree property. That is if you start with the search tree, you start within tree where at every node stuff to the left is smaller, the stuff to the right is bigger. You insert something and you follow this procedure. You will still have the search tree property after this new node has been inserted. That's something for you to think through.