Hi in this episode we will learn what is a binary tree and why are they so useful.
Then we will learn how to implement one and also during this implementation we will cover a very powerful
programming concept which is recursive functions.
So far all of our examples has been using media data structures which means that elements on the data
structures are sequential like this.
So we have 10 8 20 9 0 15 and 25.
All of these items or elements are on the same level binary trees are part of what it's called Tree
structures.
So rather than having a single level items we have a hierarchy like this.
So compared to the previews like literally the structures are tree has different hierarchies.
So in this case eight is US Chamber of 10 as well as 20 and so on.
So a binary tree is a tree where every node passed and most to Children's.
So how do we build a binary tree.
Let's say we want to convert the linear destructor into a binary tree.
So we start with the root node which is 10 and then we have to up the node number 8.
So we will compare estate less or equal than 10.
If it's lower than 10 we will add these to the left.
No otherwise we will add this to the right note.
So A is lower than 10.
We will have this item to the left side now 20.
What happened with 20 20 is bigger than 10.
So all of these to the right note.
Now here comes a special case will happen with 9 so we start on the road again and we will compare 9
with 10 is 9 lower than 10.
Yes someone wanted to go to the next node which is good child node often is 9 lower than 8.
No.
So we will at this to the right side and so on.
So the same for 0 will go through 10.
It's slow when we go to the left we go.
We compare with 8 is slower we go to the left 15 is bigger than 10 but it's lower than 20 and 25 is
bigger than 10 and bigger than 25.
So why are binary trees useful basically for searching.
So if we have a dataset like this but instead of having seven items we have millions of items.
If we want to look for the item twenty five on a linear destructor we should check for every item in
this case he's twenty five people at that no he's twenty five.
He was to wait no until we find it so we will have to do seven operations which means that the bigger
the size of the set the harder to find it.
In contrast in the binary tree what we do is rather than traversing the whole tree we go and we said
is twenty five bigger or lower than ten.
What is bigger to the right now the moment we go to the right.
We don't have to check any of those items because we know they are smaller than twenty five.
So we split the set in half.
Now we'll just have three left items to traverse.
We compared twenty five with twenty.
We know we have to go to the right.
So we don't have to check any of those on the left side.
And finally we find it now on the smaller samples.
Doesn't make too much sense or you probably won't be able to see the difference.
Then when you have massive datasets like databases they use these sort of algorithms to make it very
more performance.
So let's get started with our implementation.
The first thing I wanted to do is defined tree structure.
So let's say tree and the tree will contain a node.
OK.
Now what is a..
I know it's a ghost truck which contains a volume.
Let's use it as we've been doing and then we said that a binary tree has either left or right.
Children.
So let's do left will just hold on.
Right.
Which is a node as well.
Okay.
And let's define a main function.
Okay.
So far so good.
The first operation we will introduce is is our right for adding values and these will receive value
of pi.
It is interesting it will return our tree.
Then you will see why.
So far let's just return ourselves.
Right.
Okay.
So how does this works.
First we will verify that the node of this tree is not empty or kneel and if it's empty which will be
the first gate where we need to align our tree we will do the node equals to know the value value.
Right.
So we're creating a node otherwise we will do to.
No.
Is there value.
Okay.
And then we return ourselves.
So now we're calling the insert from the node which means that node needs to implement an insert function.
Right.
So that's the same.
Okay.
So what we're doing here is the following.
First as we just saw in value is lower equal than the current value.
We're going to the left right.
Otherwise we're going to the right.
Okay.
So let's assume we're going to the left.
Wait.
2 verified cases that the node doesn't exist which means no Neil.
Isn't that like the example when we are the number 8.
Right.
We went to verify 10 and the left side is nil.
So we will create a new node on the example that will be 8 with value.
OK.
Now let's say there was a value on this on the left side.
All new and the left insert the value.
So what's happening here.
I told you in the introduction.
This is what's called recursion which means that node defines an answer function and inside that function.
I'm calling the same function the now my node points to a different note.
Okay.
So for the right place is pretty much the same which means that E and the right doesn't exist.
We will create a new node
all the Y and the right user recursion again value.
Okay.
So let's revisit this function again.
This is the first operation we compare the values a binary trees has a child which says that is the
value is smaller than a specific one we go to the left which is this case the other child.
Sorry if the value is bigger or else we go to the right.
Right.
So we have these two children.
So now we should be able if everything is fine to create a tree.
We'll use this notation and then we will insert some values the same on the example so insert pen and
then we should do to the user eight twenty nine and so on.
But if you remember insert is returning the same tree so all we could do like a shortcut here and ask
insert is returning the same tree we could change these methods which is the use for 10 dot E's or 8
but instead planning and so on.
So this is really handy where you want to do many operations of the same type you want to change those
methods and also go through boards to do multi line chaining which is you can up every method call in
a different line so it reads pretty nice and easy so let's insert number nine member 0 15 and finally
twenty.
OK.
So let's run this and make sure everything is going well.
Yeah.
Nothing happens because we're not bringing anything but at least he's not breaking anything.
OK.
So let's try to bring this let's define a function call brains know which receives as an argument.
I know and doesn't return anything.
So the first case we might have empty nodes right.
Which are like the children's of the last node by the way.
The last nodes on a tree are called Leeds.
So the first thing I wanted to check is that.
No it's not empty.
You can something we just return.
And now little bit more about recursion.
We will first bring the value of know and then we will print it its Childs so how do we print an on
again print.
Note the left side means no the right side.
OK so again Perino we'll take an old argument probably the first note on the parent note or the root.
Now we know that the group No 10.
In the example we just saw has two children.
So we will print the left one and the right one and we're going to use the same function.
This is recursion again.
So let's call this function and see what happens.
Green No dy no yes we would have seen things that are which is here because we'd run businesses.
OK so let's see how this works toward bringing 10 8 0 which are all the left to children.
Then we go to nine twenty fifteen and twenty five.
OK.
So if you compare these with our example you will see that the implementation is going to the left first
and then to the right well this is pretty much it actually.
So let's review this.
We create an oak tree which has the eastern method which is its items and also we have a print method
which brings the whole tree.
Now we also said that binary isn't very useful for efficiently looking for values.
Right.
So let's implement a method on the Node practical exists which even a value will say if that value is
part of the tree or isn't right.
So again it's pretty similar to print.
First we need to make sure that the node is not empty or otherwise.
If the road is empty there's no value.
So this will be false.
OK.
Now if know the value is equal to the value that we're looking for in this case value plus true.
So return true which means that yes the value is not what happened with my children.
What I need to do is again in value lower or equal than you will never be equal actually because that's
already very high here that the no value.
That means I need to verify the existence with my left now with my left side.
So I go to the left node and collect.
Otherwise I'll go to the right side and call X's right yeah.
I need to turn these OK.
So let's read this function one more time.
Even only something I assume I'm on the leaf.
No.
So there's there's no more no to verify the value wasn't found.
Is the value that I'm looking for is the same then the notes value true value exist in my tree.
And then we're doing the binary operation which is is the value that I'm looking for lower than the
current one.
Yes.
So I'm going to the left.
Otherwise I'm going to the right.
Now let's try this out.
Let's say you know it says let's say twenty five.
Why not.
Oh green line.
And this should be true because I've already a certain value here and it's true.
Right.
Now let's try to look for a value that doesn't indexes which will be 26 and it's false.
Now let me just remove this if we want to check the no that has been evaluated on the look up of this
value.
We could go to the sixth function and just print the value of the note here.
This is just to make sure that we're not traversing the whole tree while looking at the value so ok
for looking at value 26 we're traversing for no number 10.
Which is the root node.
No no 20 and no no twenty five.
So we're not going through any of the smaller one which shows the efficiency of the binary tree.
So this is it for this episode.
And with it we conclude with the section number three which is data structures.
I hope you've enjoyed and learn and see you on the next one which is the most exciting section of this
course by.