All language subtitles for 13 - How to Construct a Binary Search Tree English

In some past videos I've talked about binary search trees and how to put them together.

However I took a data set that was very well structured and so the tree was nice and balanced.

And then in some of our other videos we went over red black trees and how to balance a tree that wasn't

really structured the way you'd want a red black tree to be structured in this video.

I'm going to show you how you can take an array and how you create or construct a binary search three

tree based on the elements of that array in their original order.

So you can see on the right hand side here we have an array with elements 5 7 1 15 9 2 14 8 7 and 3.

And so if we're going to create a binary search tree with this array they have to actually go in order

and show you how that works.

So the first element in our array is going to be 5.

And so it's an ICC we create 5 and put it inside of the at the root node.

The next one we're going to use is going to be 7.

And because seven is greater than 5 we'll do that comparison and then you'll put 7 on the right hand

side right next to 5.

After that we have a one.

One is less than five.

So it goes left and right here we have a very nice basic tree structure.

We have our root node.

We have one bean the item or the node to the left seven to the right.

So far everything is normal.

Now we're going to add 15 15 is greater than 5.

It's greater than 7 so it needs to go all the way to the right.

Now I'm just going to start adding some more in order in the array.

So we go 5 7 15 now nine is less than 15.

And so we put it there on the left.

Now if you are familiar with red black trees or some of these more self-balancing trees you would know

that this is not the way this would have been constructed it would have rebalanced itself and would

have swapped out the nine right here so the nine would be connected to the five the seven would be on

the left hand side 15 on the right hand side.

However this is just a regular binary search tree.

So we have to treat it as such and we have to add the elements in order.

And this is the reason why people created things like red black trees was because as you'll see here

in a minute this tree is going to look pretty odd in a short period of time.

So next element is to use less than 5 so we know it goes the left.

It's greater than 1.

So you get pulled over into the right and we're going to add 14 is greater than five greater than seven.

But less than 15 so it's going to move in the left and it's greater than 9.

So you'll see that moves all the way to the bottom of our binary search tree.

So at 14 we have just three elements left.

Eight it's going to traverse the tree we see that it's very than seven but less than 15 and less than

nine.

And our last or second last one is seven.

Now that seven is an interesting one because you can see that it is greater than five it's actually

equal than seven but because it's equal to seven it's not less than seven.

It gets moved.

It goes to the right.

It's less than 15.

Less than nine.

Less than eight.

And it goes right here.

So even though these two nodes are actually the same value one is directly descendant of the root node

and the other one is all the way here.

Now it is the closest node to the 7 because they are equal and so it's neat to see the way that that

automatically happens but it's still pretty important to see that you can have a tree that is structured

like this.

If you take everything in order and last one we're going to do is a 3 and that's greater than 1 greater

than 2.

So it gets pooled here.

And so given this data structure here on the right and side this is what a visual representation of

the tree would look like.

So you can see it's not balance.

However it is properly structured.

If you were to run a search on this.

So say that we want to define eight.

So if we want to find 8 they will go to 5 7 15.

It's less than 15 so it knows and look to the left is less than nine.

And there it is found the element.

So this is how you construct a binary search tree given in an array.