Introduction to Binary Search Trees

This is not a coincidence. Any node to the left of 49 must have a value smaller than 49. Any node to the right of 49 must have a value larger, greater than or equal to 49. If they rule, binary search trees must follow. Now, that being said, since 38 and 62 are the children, by definition, that makes 49, the parent node. And since 38 and 62 have the same parents, that makes them siblings. And it doesn't have to stop there. 49 is not the only node allowed to have children. 38 and 62 can also have zero, one, or two children over their home. Fan go for 24, 41, 55, and 73, so on and so forth. All right, now why would we use a binary search tree? Why can't we just use a link list or a sorted array list? Why bother with the binary search tree? Well, the reason being is that linked list and sorted array list while they do have their strengths, they also have their weaknesses and what a binary search tree does is combine the best of both worlds. Now, what are these weaknesses I'm talking about? Well, suppose I have a sorted array, and I want to insert the number 7 into this array. 

Now, clearly, the 7 is going to go in between 5 and 9. But I can't just wedge an empty space between 5 and 9. Memory does not work that way. If I want to insert 7 in between those two numbers and I'm going to have to move each number from index for one and beyond to the right one, one by one before I can fit 7 into the array. Now, if my only has 6 or 7 values, this is not a big deal. But if I'm Google and I'm using a container that's storing a millions upon millions of values, then this operation can become very, it can become a relatively time consuming. Same thing goes if I want to remove a value. Suppose I want to remove the number 13 from the array. Well, I don't want to just erase index three and leave a gap there. I want to close that gap, which means I'm going to have to move all the numbers behind it up one spot, which once again, if I'm working with a very large array, this is going to become a time consuming process. That was linked lists. We know that with linked list, if I want to insert a value or remove a value from a linked list, it doesn't take long. It's just a matter of creating a new link object, manipulating a couple pointers, and then we'll do it. So link list with linked lists inserts and removes are not the issue. 

However, I can do a binary search on a linked list because linked lists don't provide indexes like arrays do. If I want, if I'm going to search for a value in a linked list, I'm going to have to do a old fashioned linear search, which means studying at the front, then checking the first value, then the second, so on, and so forth until I find the value I'm looking for. And again, if my link lives the story millions of values, this can be a very time consuming process. Binary search trees, as you will see later down the road, do not have any of these issues. All right, well, before we get into how binary search trees work, let's just introduce some more vocabulary. So here's my entire tree. The node at the very top of the tree, we call that the root of the tree. All right? Now, if we look at, if you look to the left of the root, you'll see a miniature. You say 28 is the root of that mini tree. And if you look to the left of 28, we can find another miniature of which 18 is the root of. These mini trees we call subtrees. A subtree, if any tree consisting of a node, that node children its children's children and so forth. The roots of a subtree does not have to be the root of the entire tree. Another important word is the word path. Now what do I mean by path? By that, I mean, suppose I ask you, how do we get from note 50 to node 55? Down at the bottom. And the only way we can get there is to use the edges that connect the nodes. 

Well, there's only one way to get from 50 to 55. To do that, we'll have to go to 74. Then the 62 before finally reaching 55, thus the path consists of note 50, 74, 62, and 55. A path is the sequence of nodes that must be visited in order to go from point a to point B on a binary search tree. In front of you is a node with zero children, a node that has zero children. It's called a leaf node, and no a leaf does not have to be by itself in the tree. Even in a big tree with many nodes, the node that you see at the very bottom that have no children, those nodes are called leaf nodes. In other words, you may hear me, youth often is the word to visit. Usually when I say I'm visiting a node, that means I'm doing something important at that node. It could mean I'm printing the value at that node or maybe I'm modifying the value at the end of it, or maybe I'm deleting that node, perhaps I'm removing it from the tree altogether, or I'm inserting a new node in its place. Anytime you hear me say that I'm visiting a node, that means I'm doing something significant at that note. And the final book I believe a word is the word traverse to traverse the binary search tree means to visit each node in that tree and the specific order. There are several ways to traverse it binary search tree. We're going to discuss each way and each way is very useful. Depending on what exactly you're trying to do with that with the search tree at that point in time.