[MUSIC]

So let's think about what the maximum distance in the tree,

what is the maximum distance between the root and a leaf?

Because when we fall off the tree, that means that we've reached a leaf

node in the tree, one that doesn't have any children, and then when we try to go

to a child we get that the node is null, and so then we return false.

Okay, so in these three different examples of binary search trees,

with the same dictionary,

we notice that we have very different maximum distances from root to leaf.

So the green tree is the worst, in terms of how far we have to go down.

It contains all seven nodes in a single path, and so the distance in the tree

is the number of nodes in a single path from the root to the leaf.

On the other hand, if we look at the tree with yellow nodes,

we notice that there's always really short paths from the root to the leaf.

And so if we look at each of the leaves, there's three leaves,

each of those are accessible using only paths that have three nodes.

So to get to the leaf that's labelled a, we go from the root ate to the node at,

and then to its child node a, and a is a leaf node.

And similarly to each one of the leaf nodes we can hop

with only three nodes in our path.

Now, we can have a binary search tree just sort of in between, and the blue one has

a path that has four nodes on it, and so its maximum distance until a leaf is four.

So this maximum distance notion is called the height of the tree, and

we notice that we can have trees that have the same number of nodes all together but

have different heights.

And now thinking back to our example,

we notice that the height really impacts the performance.

And so what we'd like to do is to control the height.

We want to keep the height down as much as we can

while still maintaining the same number of nodes.

And this is where balanced binary search trees get their motivation.

This is why we have balanced binary search trees.

The idea is that we want to maintain roughly the heights of the left and

right sub-trees of our trees, so that we never have these really long,

long paths that we might have to traverse while looking for

a single element that might not be on the tree.

And so, a tree, a binary search tree is called balanced if at every node in

the binary search tree, the height of the left sub-tree and

the height of the right sub-tree differ by no more than one.

All right, so let's work through some examples and

here are a few that you can think about with an in-video quiz.