Hi everyone.
So we have understood what trees are.
Now let's try to understand binary trees.
Now there are various types of trees, and the most common types of trees which you will encounter in
coding interviews is about binary trees.
So let's try to understand what these are in this video.
Now a binary tree is a tree where each node can have at the most two children.
Now, at the most two means every node can have zero, 1 or 2 children, but it cannot have three children.
Now let's take an example.
Let's say we have this tree over here.
Now you can see that over here every node is having at the most two children.
This node has two children, this node has zero children and this node has one child.
So yes, this is a binary tree.
But if you take a tree which looks like this, you can see that this node over here is having three
children.
And therefore this over here is not a binary tree.
So we have understood what a binary tree is.
Now let's take a look at these four concepts.
We'll try to understand what is the height of a binary tree.
What is the depth of a tree?
What is the height balanced binary tree.
And then finally we will try to understand why the height of a balanced binary tree is equal to log
n.
And then you have to floor it.
All right.
Now flooring means you're rounding it down.
For example, if you find that log n is equal to 3.2, then when you floor this this becomes three.
So the fourth point over here is that the height of a balanced binary tree will be equal to floor of
log n.
So in this video we will try to develop an intuition for this.
And then in the next video we will try to look at a more rigorous mathematical proof for this.
So let's go ahead and cover these four points.
So first we start with the height and depth of a binary tree.
And again over here you can note that when it comes to the depth of a node you can also call this level
of a node.
All right.
So let's take an example to understand this.
So over here we have a binary tree.
Now first we are going to analyze the height and then the depth.
All right.
And when it comes to the height there are two things that we will take a look at.
We will take a look at the height of a particular node.
And then we will take a look at what is the height of the complete tree.
Similarly for the depth, also, we will take a look at the depth of a node and the depth of the tree.
So these are the four points that we will take a look at over here.
Now let's get started.
Now when you take a node and let's say you want to find out the height of that particular node, that
is nothing but the number of edges on the longest path from that node to a leaf node.
All right.
So this is what you call the height of a node.
And then the height of the tree is nothing but the height of the root node.
Now let's try to understand this from this sample or example over here.
Now for each node let's write the height.
So if you take a look at that you can see that these are the heights of these nodes.
So let's try to understand that over here this is a leaf node.
And then if you want to go from this node to a leaf node you don't have any edge right.
So over here the definition of height is the number of edges on the longest path from the node to a
leaf.
So that's why the height of a leaf node is equal to zero.
Now if you take a look at this node over here, and if you want to go to the leaf node that's over here.
Right.
And then you can only go in this direction.
You cannot go all the way back and then come to another leaf node.
So that's why you from this node you have only one way because it has only one child.
And then if you want to go to the leaf node there is one edge right.
So there is one edge over here.
So that's why the height of this node is equal to one.
Similarly, if you take a look at the height of this node over here, you can see you have one.
And then you have one more edge right.
So you have two edges.
So the height of this node over here is equal to two.
And this again is a leaf node.
So the height of this node is equal to zero.
And when you take a look at this node over here now there are two ways in which you can go to a leaf
node.
You can either go in this direction and reach six, or you can go in this direction and reach two.
But then the definition says that the height of a node is the longest path from the node to the leaf.
So we take this direction and then we have one, two and three.
So there are three edges.
So that is why the height of this node is equal to three.
All right.
And similarly the height over here is zero.
And over here is zero because these are leaf nodes.
The height of this node over here is one because there is one edge.
When you go want to go from this node to the leaf, the height of this node is equal to two because
there are two edges.
And when you take a look at this node over here again you have two ways to go to a leaf node.
But then we take the longest path.
So that is this path from 4 to 11 to 5 to 9.
And you can see there are three edges.
So the height of this node is three.
And then the height of the root over here is four.
Because if you want to take either path right, whether you take the left path or the right path if
you take the longest path.
So that's one possibility is this route.
So you have four edges or you can take this route also.
Right.
Again you have four edges.
So the height of this node over here is equal to four.
So we have understood what the height of a particular node is.
And then if we want the height of the tree of this complete tree it's nothing but the height of.
The root note which is equal to four.
So we can say that the height of this tree is equal to four.
Now let's make a few observations over here.
If we want to find the height of this node over here, notice that you just have to find the height
of its children, which is two and zero, and take the maximum among the two, which is two.
And then you have to add one.
So two plus one gives you three.
And why is that so?
Because when you go from this node to this node there is one extra edge over here.
Right.
So that's why we have to do two plus one and we get three over here.
All right.
Now let's proceed.
So we have understood what the height of a node is.
And we have understood that the height of the tree is the height of the root node.
All right.
So remember when you are finding the height of a node you are always going down or to the leaf.
Now what about the depth of a node.
The depth of a node is nothing but the number of edges from the node to the root.
So you are going to the root which is going upwards.
All right.
So that's the difference between height and depth.
Now again if you want the depth of the tree then that's nothing but the height itself or the maximum
depth of the tree is equal to the height of the tree.
All right.
So if you want the depth of the tree that's the maximum depth.
And that will be equal to the height itself.
Now let's go ahead and try to understand this from this example over here.
So we have each node.
Let's try to find the depth of every node first.
All right.
So let's write it over here.
Now let's start at the root.
Now again the definition says it's the number of edges from the node to the root.
So when you're starting from the root you are already at the root.
So there is no edge if you want to go to the root right.
So that's why the depth of the root node is equal to zero.
And then if you come to five and four if you want to go let's say let's take one example.
If you want to go from five to the root node right you have to traverse one edge.
So there is one edge over here.
So that's the definition right.
Number of edges from node to root.
That's why the depth of this node over here is equal to one.
Similarly the depth of this node also is equal to one.
Now from this node which is three, if you want to go to the root you have to go two edges one and two.
So that's why the depth over here is equal to two.
Similarly for this node also the depth is equal to two because again you have to traverse two edges
one and two right to go to the root node.
Similarly for these two also the depth is equal to two.
And then when you come over here if you want to go from this node to the root node, there are three
edges one, two and three.
Right.
So that's why the depth over here is three.
And over here also the depth is three.
And then from this node to the root node you will have to traverse four edges.
So the depth over here is four.
And the depth over here is also four.
Now you can understand from this why we call the depth of a node the level of a node.
Right.
Because take a look at this.
Let's make an observation over here.
You can see that over here these two nodes are at one level right.
So they are the next level when you start from the root.
So that's why instead of depth we can also say the level level of a node.
So these two are level one.
These four are at level two.
Again these two nodes are at level three.
And then these two nodes are at level four.
All right.
So we have understood what is the height and the depth of a node.
And then we have also another point over here which says the maximum depth is equal to the height.
Right.
So that's the depth of this tree.
So if you want to find out what is the depth of this tree, that would be the height which is equal
to four.
So you can see that this is the height.
So that's four.
Let me write that over here.
And the maximum depth is over here.
Right.
So the maximum number of levels you have is four.
So maximum depth is also four.
So the maximum depth of a tree is equal to the height of the tree.
All right.
Let's proceed.
Now there is another interesting point which you can note over here.
Now when we create a tree we would first create these as nodes.
And then it's left and right.
Child initially would be set to null.
All right.
So when you take a look at these leaf nodes over here they don't have any children.
Right.
So they're left and right will be actually null.
All right.
So this over here will be null.
And this over here will be null.
Now the height of a null node is defined as minus one.
And this is to make the math correct right.
Now what's the math over here.
Now let's write the nulls over here.
So we have null wherever we don't have a child.
All right.
Now what's the math?
Now the math is that we have seen that if you want to find the height of this node, for example, all
you have to do is you have to take the maximum of the height of its children and add one to it.
So over here you have two.
And over here you have zero.
So the maximum among two and zero is two.
And then when you add one you get three which is the height of this node.
So this is the math which is involved over here.
Now for this math to hold true, we have defined that the height of a null node is equal to minus one.
So how does that work.
So over here this has a height of minus one.
And this also has a height of minus one.
So when you want to find the height of this node over here, its children, both of these have height
minus one.
So the maximum among these two is minus one itself.
And then you add one to it and you get zero.
So you can see that the math still holds.
So for this purpose we have defined that the height of a null node is equal to minus one.
All right.
Now let's proceed and try to practice what we have learned.
So over here I've drawn out a tree.
All right.
And the value does not matter.
Now let's try to find the height and depth of every node of this tree over here.
And we start with the height.
And we know that the height of a null node is equal to minus one.
So let me just write that over here.
So we have null over here towards its left and right.
And the height over here is minus one and minus one.
So to find the height of this node all we have to do is we have to find the maximum height of its children
which is minus one itself.
And then we add one to it.
So the height of this node is equal to zero.
And similarly the height of this node over here is equal to one because its child's height is zero.
And then we add one to it.
So we get the height of this node as one.
Now let's proceed.
The height of this node over here will be one plus one which is equal to two.
And if we take a look at these two nodes again they are leaf nodes which is the same case as what we
have seen over here.
So these have height is equal to zero.
And then its parent over here will have zero plus one height, right?
Which is equal to one itself.
So the height over here is equal to one.
And then if we want to find the height of this node we take the maximum among these two right which
are its children.
So the maximum is two.
Then we add one to this two over here.
So the height over here is equal to three.
That's the height of each of these nodes.
All right.
And then let's take a look at the depth of every node.
Now we start at the root.
Remember the depth is the number of edges you have to traverse to get to the root.
Now you're already at the root over here.
So the depth over here is going to be equal to zero.
Now, if you proceed to these two nodes, right, there is one edge that we have to traverse.
So that's why the depth at this level is one.
Or these are level one nodes.
And over here again these three are level two nodes.
Or the depth is equal to two.
Because again you can see we have to traverse two edges to get to the root.
And then over here the depth is going to be equal to three.
Because to get from this node to the root node we have to traverse three edges right one two and three.
All right.
So again remember the depth of a node is also called the level of a node.
Again we have seen why that is so because you can see this is one level.
This is one level.
And then this is one level.
So over here every node has a depth one.
Over here every node has a depth two.
And over here every node has a depth three.
And we have also discussed that the height of a tree is equal to the maximum depth.
Now over here you can see that the maximum depth is equal to three.
So the height of the tree is also equal to three.
So we have seen that over here the height is three and the maximum depth is also three.
All right.
So we have discussed what the height of a node is, what the height of a tree is, what the depth of
a node is.
And that we have also discussed that maximum depth is equal to the height of the tree.
Now let's proceed and try to understand what is a height balanced binary tree.
Now first let's take a look at the definition of this.
Now a height balanced binary tree is defined as a binary tree in which the depth of the two subtrees
of every node never differs by more than one.
Now again, let this definition be over here for a moment.
First, let's try to understand what is the need for a height balanced binary tree.
And then we will take a closer look at the definition over here.
Now if a binary tree is skewed then computationally it's inefficient to perform operations.
All right.
Now what do I mean with a skewed binary tree.
Now let's take an example.
Let's say a binary tree looks like this.
So you have this node which is pointing to this node which is pointing to this node.
So technically this is a binary tree because you can say that every node is having at the most two children.
Right.
So this node has one child, this node has one child and this node has zero children.
So this is actually a valid binary tree.
But then you can see that it looks like a linked list.
So all the benefits that we can derive from a binary tree type of data structure cannot be obtained
over here.
All right.
So that's why we want to balance the binary tree.
And that is the need for having a balanced binary.
Now let's proceed and try to understand what a height balanced binary tree is.
Over here again I have the definition a height balanced binary tree is a binary tree in which the depth
of the two subtrees of every node never differs by more than one.
Again, when we say that depth of a subtree, what we mean is actually the height, because this is
actually maximum depth, and we know that maximum depth is nothing but height.
So we can also say a binary tree in which the height of the two subtrees of every node never differs
by more than one.
So that's one and the same.
Now let's take this example over here and understand why this tree over here is actually height balanced.
So for this let's try to find out the difference between the height of the left child and the height
of the right child for every node.
And over here I have two lines to indicate that it's actually more so that that just means that, for
example, if you find that the height of the left child is zero and then the height of the right child,
let's say is equal to one, so zero minus one, we know it's minus one.
But when we do mod of minus one that's equal to one.
So we want to neglect the negative sign if it's applicable because we are only interested in the difference.
Not whether the difference is minus one or plus one.
All right.
So that's why we have this mod over here.
Now to start with let's write down the height of every node in this tree over here.
Now we know that the height of leaf nodes are equal to zero.
So we can write that over here.
And when we proceed when we go up we just need to take the maximum height of its children and then add
one.
Right.
So the height of this node over here will be one.
And if you want to find the height of this node, that would be the maximum among zero and one which
is one itself plus one.
So the height over here is equal to two.
And similarly the height over here is one.
And then the height of the root node in this case is equal to three, which is the maximum among two
and one plus one.
So that's two plus one which is equal to three.
Now let's proceed and write inside.
Over here the difference between the height of the left child and the height of the right child.
And again we're taking the absolute difference.
Now over here its two children will have a height of minus one.
Right.
Because these are both null.
And we have discussed that the height of a null node is equal to minus one.
So in that case the difference between -1 and -1 is zero itself.
So let me write the difference over here inside it.
So that's zero.
And that would be the case for every leaf node.
Right.
Because again over here also it's minus one and minus one.
And that's the case over here and here as well.
Now let's proceed.
Now if we take a look at this node over here its two children.
This child over here has a height of zero.
And this child over here has a height of zero.
Right.
So when we subtract these two again we get zero.
So let's write zero over here as well.
Now let's take a look at this node over here.
Its left child has a height of zero.
And its right child has a height of one.
So zero minus one gives us minus one.
And then we are taking the absolute difference right.
So that's why we can say that the difference is one.
All right, now let's proceed.
What about this node over here?
Its left child has a height of minus one.
Because over here its null.
Right?
And then the height over here is zero.
Now the difference between -1 and 0.
That's equal to one right.
So let's write one over here.
All right.
Now let's take a look at this node over here.
The height over here for its left child is two and the height for its right child is equal to one.
Now the difference between 2 and 1 is one.
So let's write that over here.
Now you can see that for every node right.
For every node if you consider its two subtrees then the difference of their heights does not differ
by more than one.
So that's why we can say that this is actually a height balanced binary tree.
All right.
Now let's also take an example which is not height balanced.
Again we start by writing the heights of every node.
Now these are leaf nodes.
So they have height zero.
This has height one which is zero plus one.
This has height two which is one plus one.
And then this has two plus one.
So that's the height which is three over here.
Now again let's find the difference between the height of the left child and the height of the right
child for each of these nodes.
For the case of the leaf nodes, we know that its children will have height minus one and minus one,
right.
Because these are null.
So let's write zero.
The difference between minus one and minus one is zero.
So let's write that over here.
All right.
Now, what about this node over here?
One child has a height of minus one.
Because this over here is null and this has a height of zero.
So the difference between 0 and -1 that's one.
So let's write one over here.
Now if you take a look at this node its left child has a height of zero and its right child has a height
of one.
So the difference between 0 and 1 that's one.
So let's write one over here.
And now let's consider this node.
Its left child has a height of two and its right child has a height of zero.
Now the difference between these two is equal to two.
Right now this is not allowed.
Right.
Because over here we have discussed that the difference should not be greater than one.
So this is violated over here.
So that's why this example over here is not a height balanced tree.
All right.
So we have discussed what the height of a tree is.
What the height of a node is, what the depth of a node is.
And we have also discussed what a height balanced binary tree is.
Now let's move ahead to the last point in this video, which is to try to understand the height of a
binary tree.
Now, if a binary tree has n nodes, then the height of this binary tree over here will be in between
log n and n minus one.
And when we say log n this is actually for log n.
All right.
Now.
What do I mean with this?
Let me just quickly explain that over here.
Let's say you have five nodes.
All right.
Now log five will be two point something.
We know log four is equal to two.
And log eight is equal to three.
Now everything in between will be two point something.
Right.
So log five will be two point something.
Now we know that the height of a tree cannot be a decimal right.
So we have to floor this.
So when we floor this this will be equal to two itself because this is 2.1 or 2.2 something two point
something.
And flooring it means we are rounding it down.
And that gives us two itself.
All right.
So what is mentioned over here is that the height of a binary tree will be in between floor of log n
and n minus one.
Now let's first develop an intuition for this.
And in the next video we will discuss the mathematical proof for this.
Now when will a binary tree have minimum height?
It would be the case when the tree is balanced, right?
So let's try to understand that.
For example this is a balanced binary tree.
Now you can see that if you take any node, its left and right subtrees will not have a difference of
more than one when you take their respective heights.
All right.
So this is actually the tree that you can construct with five nodes with the minimum height.
Now again over here we are developing an intuition.
Now why is that.
So let's also take a look at the tree that we can construct which has the maximum height.
Now if you want to do that it would look something like this right.
So you can see that the height of this tree over here is one, two, three, four.
Right.
So the height over here is four.
But if you take a look at this tree over here, the height is equal to floor of log five which is equal
to two.
And again you can see it over here it's two right.
So this over here has a height zero.
This node has a height one.
And this node has a height two.
And we know that the height of the tree is nothing but the height of the root node.
And over here the height of the root node is equal to two.
So this tree has height two.
And when you take a look at this binary tree you can see that the height is equal to four.
Right.
So the height over here is four.
And again we have five nodes.
So four is actually five minus one, which is n minus one, which is what we have over here.
Right.
So five over here is n.
So this is actually n minus one.
So this is actually an intuition right.
You can see if you just have it like this.
So this binary tree over here looks just like a linked list.
Now over here because everything is going in one direction.
The height is great right.
The height is the maximum possible which is equal to four.
But then this one over here is compact because it's it's balanced.
Right.
And you can see that the height over here is just two.
And again that's floor of log n n over here is equal to five.
All right.
Now let's proceed.
And let's again continue developing our intuition.
So over here we have our balanced binary tree.
Now let's explore the relationship between the number of nodes and the height.
Now we have already discussed that the height is equal to log n.
And then you have to just floor it.
All right.
Now let's try to take a look at this and see how this works out.
Now over here when n is equal to five.
So 12345 we have seen that the height is equal to two and we get two.
When we do floor of log five, log five again will be two point something.
And when we floor it we are rounding down.
And that gives us two.
Now let's say we add one more node.
So let's say we added over here.
Now we have six nodes.
And if we do log six and again I'm not writing floor but we have to do floor.
All right.
So log six will be two point something.
Now the height of a tree cannot be decimal value.
So when we floor this again we get two.
Now let's add one more node.
So we have seven nodes.
Again log seven.
When we floor it we will get two.
Now if we add one more node we have eight nodes.
And when we do log eight that's equal to three right.
So we have already discussed why log eight is equal to three.
Log eight.
In other terms right.
In other terms if you want to find out log eight, this is nothing but asking two to what power is equal
to eight.
And the answer for this is equal to three.
So that's why log eight is equal to three.
And remember whenever we discuss log over here the base is equal to two because this is a binary tree.
Now let's proceed.
Now if we had inserted the eight nodes into the binary tree in this manner, then you can see that the
height is not equal to three.
For example, over here the height when you go from this node to this node you have one, two, three
and four.
So the height of the root node is equal to four which is not equal to three.
And we have only eight nodes.
But then the thing is that this tree over here is not balanced.
So the height of a balanced binary tree will be log n.
And then we have to just floor it.