In this section, we are going to talk about another data structure known as a binary search tree in
order to get an understanding of what a binary search tree is a beast, we need to understand that it
has three properties.
The first property is the left subtree.
Of a node
contains
only nodes with lesser
values
than the nodes key.
The second property is very similar, except with it being the left subtree that is going to be the
right subtree, and instead of it being lesser values, it is going to be greater values.
And then the third property is that the left and right subtree must also.
B a binary search tree.
So some additional terminologies that we need to understand is a root node.
It is the top level node.
And then we have a leaf.
Which is a node with zero.
Children.
So if we did a mock tree real quick, this would be our root node.
This would be our.
Left leaf or right leaf.
Now we have another left leaf.
This is no longer a leaf because now we have children here.
So this is now a subtree.
And this is a leaf leaf.
And this is still a leaf.
So now let's look at some values and see how we can insert them.
Because when you want to insert these values, there's a certain way that we need to think about it
in order to ensure.
Excuse me to ensure that our order is done the correct way.
So what we want to do is we want to insert the values.
Eight 310 one 614 four seven.
And 13.
So let's bring this down.
So the first value we want to insert is eight.
So eight is our root node.
And when we insert values, we always start at the root node and then traverse accordingly.
So now we're going to insert the value three.
So with eight being our root node, three is less than eight.
That means we go to the left and we add our three similar with ten.
Ten is greater than eight, so we will add it to the right.
So now three and ten are leaf nodes since they have zero children.
So now we go with one.
One is less than eight.
So go to the left.
One is less than three.
So go to the left again.
Now we have six.
Six is less than eight.
Three is less than six.
So six is greater than three.
So now we have six here.
14.
14 is greater than eight.
14 is greater than ten.
Four is less than eight.
Four is greater than three.
Four is less than six.
Seven.
Seven is less than eight.
Seven is greater than three.
Seven is greater than six.
And finally, 13.
13 is greater than eight.
Which is greater than ten.
Which is less than 14.
So this is what our final tree would look like.
So in here we have a leaf
leaf.
Beef.
And Leif.
And then all of these.
So three subtree is one and six.
Six is a subtree.
Here we have our subtree here.
So this is what it looks like when you try to insert values into a binary search tree.
So overall, the concept is pretty simple to understand.
So now that we have a good understanding of what a binary search tree is, we can begin implementing
one and we will begin implementing our binary search tree.
In the next lecture.