OK, so welcome to another lecture, and this lecture is going to be about binary search trees.
So you probably noticed that we've already talked a little bit about a tree, at least, at least we've
mentioned one.
That was when we did the.
Tree structure that represented the recursive calls, like, for example, when we looked at the Fibonacci
sequence recursion problem, we also have a data structure that is like a tree as well that was kind
of just a theoretical tree to help us visualize what the recursive calls look like.
But trees are a popular part of computer science, and they are in fact, a data structure similar to
what you see here.
So let's go ahead and talk about these binary search trees.
OK, so we have binary trees, and then more specifically, binary search tree is a binary tree is technically
just a collection of nodes that start at a root node, which should be right here and they can have
up to don't have to be we can have up to two children, so zero to two children, which would be a left
and a right child if you had two children.
Let's look at some more specific rules about binary search trees.
Each note of the binary search tree, like I said, can have a zero one or two children for each node
on nodes, and that nodes less of tree have to have a value that is less than or equal to X.
So you see here, when we're talking about a Node X, this value in it's left.
Some tree has to be less than or equal to it.
So if we're talking about ten here and we see seven, that is less than 10 for each Node X, all nodes
in the right sub tree have a value greater than or equal to X.
So we talked about the left Sochi being left at less the right seven tree coming off a given Node X
has to be greater than or equal to.
So we see that this is greater than as well.
And if you check out the rest of the tree, you'll notice that these rules are upheld.
Both the left and right symmetries of X must also be binary surgery.
So pretty much what that saying is that if we're let's say we're at this route node here, if we go
over here and we like, if we look, if we lift this root node and we're talking about this whole thing
as being a binary search tree, and then we go down to here to seven and then we just looked at this
whole sub tree here that was coming off this connection.
This all has to be a binary search tree as well.
Same for everything.
Like I go here, this whole tree has to be binary search tree.
This whole tree has to be binary surgery.
So as long as those rules are upheld, then we have a binary search tree.
So let's go ahead and walk through an example of inserting some numbers into this binary search tree.
So I have a list of numbers.
I'm starting from left to right and inserting them.
So we start out with 10 that becomes our root node.
So the first thing that you have that you're inserting will be the root node.
Then we have 18, that's greater than 10.
So we branch off to the right and put it to the right of 10.
We have seven, which is less than 10.
So we range off to the left, so you can imagine seven came in here.
We compared it to 10.
We said, OK, seven is less than 10.
So we put it here.
We have twenty one, so twenty one goes here.
We said twenty one is greater than ten is twenty one greater than eighteen.
Yes, it is.
So we'll make that the right child of eighteen.
Then we have five, let's go ahead and think about that.
Five comes in to 10.
It's less than 10.
We compare it to seven.
It's less than seven, so it should be right here.
There it is, and then we have three, three years compared to 10, then we it's less than 10.
So we come here, we say it's three less than seven.
Yes, it is.
It's three less than five.
Yes, it is.
So we put that here.
Eight.
It is less than 10, and we get here is eight less than seven, no.
It's a greater than seven, yes.
So we put it right here.
Sex comes in, sex is less than 10, sex is less than seven, sex is not less than five is greater than
five, so we're going to put sex right here.
Nine comes in, nine is less than 10.
Nine is greater than seven, and nine is greater than eight.
So we're going for that right here.
Twelve thousand year, twelve is greater than ten, but it's less than 18.
So we put that here and then finally, 29 is greater than 10.
It's great in the 18 and it's getting twenty one.
So we put that here.
So basically, as the values come in, they just kind of trickle down the tree until they find their
respective spots.
So at each given node, you're asking less than or greater, then it's less than to the left greater
than to the right.
And you kind of build your tree downward like this to different branches.
OK, so let's continue on.
So what are these binary tree searches good for?
What can we use them for?
Why are they an important data structure?
Well, they're called binary search trees for a reason, and that's because they can make searching
a lot faster because of the way the tree is organized, so you might have already heard of the binary
search algorithm, or you would use that on an array or vector or something.
And you might have remembered if anyone had mentioned that the time complexity of that was log based
to an end so show of log in.
We have a similar situation with this binary search tree for searching for a number in here.
So let's take a look at that.
If we take a look at this tree, we can make some observations about the time taken to search for whatever
value we're looking at while looking at the relationship of the number of nodes and the height of the
tree.
So how many notice do we have?
One two three four five six seven.
And our height is one two.
So what we can actually say for a binary search tree like this, this is actually a perfect tree.
So that means a perfect tree is basically when it is perfectly balanced like this.
Like you notice that there is three.
There's like this exact sub tree is repeated over here and it is over here.
And when we're looking at the height compared to the nose of this, we can say that the height of the
tree or the number of nodes of the tree would be two to the height plus one power minus one.
So we have a height of one two.
And so if we do two to the two plus one, that is two to the third power that is eight and eight minus
one is seven.
And we notice that we have one two three four five six seven nodes.
And we haven't gotten into a detailed algorithm analysis yet, but I keep hinting that we are going
to go over that in the future.
But if you were to analyze that in a more poufy kind of manner, you would notice that the time taken
to search or insert is actually log base to end because the tree is like this.
So the that's why we have here at the time, taking the specific tree is a log in because the height
is long.
And if you were to look at that to to the height plus one power minus one and kind of solve that, mathematically
you could see that.
And that, of course, is where we're considering and to be the size of the input, which is also the
number of nodes.
So it is oh big oh of log in for the best case and average case time complexity for both insertion and
search operations in the binary search tree.
But what about the worst case then we talked about it being Lord big of log in for the average and best
case.
Well, think about what would happen if we built a tree by using our input like we did before, but
our input was coming in an ascending order.
Or descending order?
So, yeah, right here in this example, we have a descending order.
So what would that look like?
Think about that for a second, maybe pass the video and see if you could draw that out on paper before
I go over it right here.
OK, so if you did draw that on paper and let's see if you got something similar.
So we start out with 10, eight comes in, it's less than 10.
We do a less surgery, then we have seven coming in seven, six and 10 of us and eight.
So we put it right here.
Five coming in five or six in 10 five is less than that.
Five is less than seven.
We put that here.
We could keep going, and if you ended and if this were still in descending order, but you can kind
of see a trend here.
So do you notice anything familiar about the way this binary search tree looks?
Think about data structures that we've already gone over.
So you might be saying, hey, this kind of looks like a singly linked list and basically is and the
problem with this is if we have it in this order, that means that searching for something becomes similar
to how we would need to search for something in a linked list.
And instead, we have to pretty much do like a sequential search at this point, which is going to be
linear time.
And so it's going to be big of in instead of of log in.
So the worst case to search and insert as well is going to be big go of in linear time for binary search
tree.
OK, so let's go ahead and think about how to traverse this binary search tree data structure and what
we're going to do is put this new concept that we just learned recursion to use to traverse this tree
in a few different ways.
We're going to cover three major types of reversals in this lecture.
And it's going to be in the context of printing all the values in the tree.
And so I have some I have these three listed here.
When you see the word current that is so synonymous with us printing the value in the tree, so I'm
saying print something, print the data at the current node.
Think of it like a linked list node and you had that data member.
We're going to go ahead and print that data member at the node so you can compare it to what we've done
with link lists so far.
And then the left and the right are, of course, respectively.
You know, here in here, like going to the left cemetery in the cemetery.
Just talking about the what we're doing and what order we're doing things, so, you know, this is
like print the current value, then take a left, then take a right in order traversal would be take
a left.
Print the current value.
Take a write post.
Order would be take a left, take a right and then print the current value.
So that's what I'm talking about here.
OK, so I'm going to do a major like slow walk through all, go over all the details and kind of walk
through of this pre order traversal algorithm just so we can get really good understanding of what's
going on with these recursive algorithms to traverse the tree in the next to the in order and post order.
I'm going to kind of just go over those in a little less detail, so I'm not going to, like, show
each line executing and what's happening.
I'm just kind of kind of show what order the nodes are going to be printed in and just step through
it that way.
So let's go ahead and start.
We're starting out at the root node.
You see that this node is being passed here, so you can imagine that this node gets passed here.
And then we start this function.
We start this preorder traversal algorithm.
So what we're seeing is the no no.
If it is returned the notice, not no, we're all good here.
This is not a no.
OK, so then we come right here.
The note is not null.
We're going to go ahead and print out our data here, which is 10.
Then we're going to hit this line here, and we're going to recursively call the function and pass the
nodes, the current nodes left some tree, so we're on this node.
We're going to pass it the last century, which is going to lead us to this node.
So this is the node that we are passing to our function recursively now.
So now we're on here, you see the green arrow denoting where we are.
If the note is null, then return the notice, not null.
We're going to go ahead and print out the value at this node.
Let's do another recursive call with the left sub tree.
So now we're here the nodes, not no.
We're going to print that out.
Another recursive call with the left sub tree.
So now we're here.
It's not north, so we printed out the native value there three.
OK.
Let's go to the next one.
Another recursive call, we're going to pass the left sub tree.
But you notice that we have a red arrow there, and it's pointing to no.
So similar to the linked lists at the end of the linked list coming off the tail, remember we had a
null pointer, so it's going to be similar here in the tree with three in this specific example has
a no pointer for the left side tree and for the rates of tree, so it's pointing to null.
It is null.
So we hit that line and it says return and we return and we go back.
We came to it back to where we were, we came from that print pre-order, no less arbitrary call.
Now we go down one line since we returned to that last February call and is saying recursively, call
it right century.
We already said and mentioned that the cemetery is also known as an old player.
So we're going to return and we're coming back.
We're going to go back up now to the five.
And we've already explored the left.
So we're going one line down and we're going to explore the right, so recursively call that now we're
at six, it's not.
No.
So we're going to print out the data.
We're going to take left cemetery, but it is a leaf node, like we mentioned out before, I called
those leaf nodes in the recursive tree.
We're going to use that terminology here as well.
These.
This is a leaf.
No, this is a leaf node.
This is a leaf node and this is the leaf node because they are at the bottom and they just have these
node pointers coming out of them.
OK, so that is all so we return back.
Then we say, hey, let's check out the right subject.
That is no.
So we return and now we return all the way back up here because we've already explored all these left
and right and printed out stuff.
So now we're coming all the way back up our stack frames to here.
OK, so we're on seven.
We already explored less of trees, so we're going down the right sub tree.
We recursively call that that moves us to eight.
It's not no, we're going to go ahead and print that out.
We're going to check out the left, some tree.
Oh, left, some tree is no.
So let's return and we go back to eight.
Now we're going down right, sub three.
Some trees, not no.
So let's print that out.
So less of a tree, there's a leaf node, so it's now your turn back.
Right?
Some tree also know we're going to return back and now we've already explored the left and right all
the way down for this seven node.
So now we're coming back up to the root node here.
So we've already explored the left.
You notice we came back here to this last century.
We're returning back to this point in time where we've already called this.
So now we're going to go explore the right.
So we hit the right, some tree.
Now we are at 18, and it's not, no, so it's apparent that.
Let's check out the left Sochi, we go to 12, it's not know we're going to print that out.
Now we're at Alief, so that's going to be no.
So we're going to come back, we're going to look to the right.
That's also no.
So we're coming back up to this node.
And then we look at the right sub tree.
That is Noel.
And then we're pretty much done because it came back to the recreation of here and we printed everything
in our pre order traversal.
OK, so hopefully that was detailed enough for you to kind of understand how we go through the tree
with recursion.
Let's go ahead and check out the next one.
So this time I'm not going to step through with detailed, but we're just going to talk about in what
order the nodes print.
So you notice now we're doing in order to rehearsal.
So we have house.
I wrote a note here, just like before.
But what we are doing is we're doing a less arbitrary recursive call and then we are printing our data
in the middle and then we are doing a right summary call.
So I'm just going to step through it because it's just going to tell us what the the green arrow will
denote, what is getting printed first and what order.
So we start here.
We're going to have it's not no, so we're going to have a left Sochi call, so it's going to go here.
This is not normal, so it's going to have another massive recall.
This is the first thing.
So we're just going to keep taking left, so left, left left and then we're going to go all the way
down and it's going to be null and then we're going to come back.
And then once we return back to here, we'll be going to this line.
And we will print out our data, so we'll be printing out three.
And you notice that I am not having that there, but then what we do at that point is we are doing our
right obituary.
So sorry, I kind of jumped ahead there, but we print our data.
We do the right century right of trees and also we return back.
And we're going to return all the way back to here, and we already checked out the left cemetery for
here, so we would go down to the next line and we would print out the data here.
So that's what this is for and saying now we're printing five.
That's where we're at.
Then we're going to check the right cemetery.
So we go down to the right cemetery.
And so that gets passed up here.
And then where?
So we're right here.
And then we hit the left cemetery recursive call.
So we would check out left.
Oh, it's no we would come back.
Since we came back from this left cemetery, we go to the next line and we would print out the data
here.
OK, and then we would check out the rates of tree would be no.
We'd come back and return all the way back up to here to this seven and then we said we'd be right here
and then we come down and we would print our seven right here.
Then we would hit the right cemetery of seven that hasn't been explored yet.
It would bring us down to here.
We had the left cemetery it is now.
When we come back, we'd print the note.
Once we printed the known, we check out Right Cemetery.
We'd be at nine.
Check out Left Cemetery, it's no we'd come back and then we'd print out.
This right here, the nine.
We explore Nine's right century.
It's a leaf, so there'll be no when we come back here.
After explaining, right, some, we go all the way back up.
We've already explored all these, so we go back to the root.
The real Arctic's for the left, so we come back to here, we go to this line.
So you notice that I'm coming back, you know, when I say we come back to here, we're going back to
those previous stack frames.
That's what I'm talking about.
So we go ahead and print out 10, which is our route node.
Then we even head up to right some tree.
We go over here.
Sorry, I click too early again.
We do the right.
Some tree.
Then we would do this left some call.
And it would be 12, so we would print out 12, then we would do the right sub tree, then we would
do the less arbitrary.
We would come back up.
18 would be the next thing printed.
And now we've printed all of the nodes in the tree.
So that is an order traversal.
Now, let's check out post order traversal that's going to be left, then right, then print the current
note.
Same thing we started out now we do in both recursive calls before printing, so it's can do the same
thing where it does left first, so it's going to go all the way down left.
So we're going all the way down here and it's going to hit nil and it's going to come back here and
then it's going to do right and then it's going to come back and then it's going to print the data.
After that, it's going to come back up to here and it's going to go right because we're coming back
to this left.
And it's going to go right.
And once we do, the rates of tree.
Call.
Then let's see who we'd be on five.
It would do the right surgical and then it would print out the notes data.
Then it would come back.
And then we have already done left and right for five.
So it would print five data.
OK, so then we would come back and we go all the way down here because we've already explored all the
left of seven, we're going to do the right cemetery cause we're going to go all the way down here.
And once we've gone down all the way on the right centuries, we have our data afterwards.
So we'd print that.
And then we're coming back and we're printing this because we're recursively coming back, we've already
done the left.
We would actually do to the left of this and then, yeah, so that's already printed out.
Then when you do seven.
Coming all the way down and we've explored the left from the root, so now we're going to have to come
down here to the right and then we have our left some free call first.
So we're going to hit this up first and then we'll come back and hit this up.
And then finally, it will print the root node.
So hopefully that makes sense for you.
And then step through in as much detail, but you can kind of get the gist after looking at that first
one is kind of where we place this print in relation to our left and right submarine cars.
So they're useful for different things.
Sometimes if you have trees that are holding like mathematical expressions, this post order can be
a nice thing to be used to print it in a certain way.
Most of the time, though, we're going to care about in order traversal because we want to print these
values in their sort in order.
So that is something that we will be implementing in code.
You already saw an implementation here, but we're going to go ahead and write that in code as well,
and we'll do some other recursive functions.
As well.
OK, so that is actually all I have for this lecture.
We're going to get right into writing some code for this binary search tree and we will look at 13 functions
and a few other things we might get into deleting as well.
But hopefully it gave you a decent overview of the binary search tree.
There are multiple types of trees, and they don't all necessarily have to be made up of like pointers
like a link list like pointers and knows some of them can be implemented as an array and things like
that.
And then we also don't always necessarily need to do a recursive algorithm for some of these to reversals.
It is possible to do an iterative solution sometimes.
And do some different reversals, so we might look at that as well, that's a little more challenging
actually to most students.
So we'll get into that and kind of push ourselves to figure out some iterative solutions as well.
All right, I hope you enjoyed this lecture and I will see you in the next lecture.