Hello all and welcome back.
So in this video let us now continue our discussion on Bsts.
And now let us see how can we define a BST node.
So let's get started.
Now before we begin on defining, let us first discuss that.
What is exactly the structure of my BST?
BST is just like Binary Tree are having a left child and a right child.
It is some property which we are enforcing on it, but that doesn't mean the structure or the way we
are printing as well is going to change for my BST, right?
I am just saying that once the structure is ready, or once you have defined a particular binary tree
in the same structure.
Of course, with having a left and the right child, you should just follow this property and then I
will see you on a BST.
Okay, so ideally, as we discussed as well, it is a special kind of binary tree only.
But yes, it has some property which we have enforced on the same.
So the structure is actually going to be exactly the same as it was for a binary tree node.
But still, to make sure that we have this overall idea and a differentiation, we will make sure that
we are able to define this node with a name of class BST node.
Okay, so let's go to the VS code and just define the same.
So this is the best node and printing everyone class.
BST node I'm defining in this we will have a constructor.
In this constructor self and data.
Great.
Now what I have to do self dot data is going to be equal to my data self dot left none.
And self dot right equals none as well.
Okay everyone.
So I hope this is clear.
Exactly.
Same structure.
just that we are saying it's a BST.
The reason for that is because I want that.
Okay.
If someone sees that it's a BST, he doesn't make any changes to my trees overall.
Okay, great.
Now let us see how the print function will work with respect to a BST.
I believe that for printing we can use in order.
Okay, so let me just explain why that can be true.
So we have discussed about all these in orders and pre order and post order.
They are all the traversal different traversal the way we can do on our binary trees.
Now when I'm talking about BST okay.
And I have defined let us take an example only rather.
So let's say we have a BST something like this.
Let's say it is three here.
Here it is four and here it is two.
Similarly this side We have eight here, six here and here.
It is ten.
Now when I will be making the overall in order of this particular tree, I will be traversing something
like this.
So I will first go here in order says that first the left subtree, then me, then the right subtree,
or first the left side.
Then please pull me in and then the right subtree right.
So if we see this it's going to be something like this two.
Then we can go back here three will say that okay you are done with my left part.
So now print me and please.
Now go to the fourth part and fourth it will go back.
Now five will say okay, if you are done with my left part, please print me and then go to the right
part.
Similarly, eight before printing will say that hey, please first print the left part, then you can
come back to me, print me and then go to the right part so you will see that it's a sorted.
Overall nodes.
Right.
And that is always going to be true.
The in order is going to be sorted for your BST, because we are making sure that we are printing in
that order.
If everything on your left is smaller, then you, if everything on the right is bigger than you and
you are seeing in that format only where you are starting from left, then you and then right, then
of course it's going to be a lot.
It's going to be sorted.
Okay, so let me just write this quickly.
The in-order traversal I think we have done this again a lot of time.
So print BST.
Print underscore BST root dot left.
Print root data.
And we used to do like this.
And then print BST root dot right.
Okay.
So this will just give me the in-order traversal.
I can say write it here as well.
In-order Traversal of my BST.
That said, it is not the case that a pre-order and post order will not exist.
Like again, they are just coming from binary trees so all this will also be there.
Along with that, we can also print it in the structure the way we print it for a readable.
But before that, let us just try to first check this out if this is working exactly fine or not.
Now for the same use case, what I have done is in the last like in the last two trees modules, we
have the predefined generic trees and binary trees.
Right.
So here I have defined some predefined binary search trees.
This is a structure which we can see.
So five 1015 it is a BST 510, 15, 20, 25, 30 and 35.
It is a BST and this one is also a BST, though it's quite long.
So we know that how we have to get this out.
So we just have to copy this.
Okay.
To get the three routes and what we can do.
I can just import.
I can just import from predefined bsts.
Import create predefined Bsts manual.
So this is the function.
And I will be getting three routes.
Now what I can do I can just do route two.
Now you could have made a BST yourself as well.
We could have taken the input but again that would have been a lot complex.
So it's always good that we are able to take these created examples.
So yes, I think we are able to see that it is sorted now one more way.
We of course used to print our trees or something like this.
So I'm pasting this function, something which we have written already.
This is the function everyone.
So in this format, if you remember right, we used to print in this particular format for the left
child and the right child.
So let us do this.
It's again preorder just that it is giving us some extra information as well.
So if we print by this preorder one second.
This year so we can see that 20 left ten right 3010 left five right 15.
And like this we have seen this overall structure a lot of time.
So yeah that is another way we can print our binary search tree as well.
Now moving forward we will actually do some questions before we jump into our BST class, because I
want all of you to get comfortable in how exactly is BST helping us?
Okay, so this is all the similarities, which is there with respect to binary trees.
But now everything which we will be doing will be different the way we used to do in a binary tree or
a generic tree.
Okay, so let's meet in the next video.
Everyone there we are going to now do operations on binary trees, which will actually help us to understand
how they are helping in optimizing our operations.
Okay, so cool.
And everyone, let's meet in the next video.
Thank you.