So what I want to do next is test your understanding about the search and

insertion procedures by asking you about their running time. So of the following

four parameters of a search tree that contains n different keys, which one

governs the worst case time of a search or insertion. So the correct answer is the

third one. So, the heights of a search tree governs the worst case time of the

search or of an insertion. Notice that means merely knowing the number of

keys n is not enough to deduce what the worst case search time is. You also have

to know something about the structure of the tree. So, to see that, just let's

think about the two examples that we've been running so far. One of which is nice

and balanced. And the other of which, which contains exactly the same five keys

is super unbalanced, It's this crazy linked list in effect. So, in any

search tree, the worst case time to do is search or insertion is

proportional to the largest number of pointers left to right child pointer that

you might have to follow to get from the root all the way to a null pointer. Of course

in a successful search, you're going to terminate before you encounter a null

pointer but in the worst case, you want insertion you go all the way to a null

pointer. Now on the tree on the left you're going to follow at most 3 such

pointers. So for example, if you're searching for 2.5. You're going to follow

a left pointer followed by a right pointer. By another pointer and that one

is going to be null. So we're going to follow three pointers. On the other hand,

in the right tree, you might follow as many as five pointers before that fifth

pointer is null. For example, if you search for the key zero, you're going to

traverse five left pointers in a row and then you're finally going to encounter the

null at the end. So, it is not constant time certainly, you have to get to the

bottom of the tree. It's going to be from proportional to logarithmic, logarithm in

the number of keys if you have a nicely balanced binary search tree like this one

on the left. It's going to be proportional to the number of keys n as in the fourth

answer if you have a really lousy search tree like this one on the right and

in general. Search time or the insertion time is going to be proportional to the

height. The largest number of hops we need to take to get from the root to

the leaf of the tree. Let's move on to some more operations that search tree support but

that, for example, the dynamics data structures of heaps and hash tables do not.

So let's start with the minimum and the maximum. So, by contrast and a heap

remember, you can choose one or the two. You can either find the minimum, usually

you find the maximum easily but not both. And the search tree is really easy to

find, either the min or the max. So, let's start with the minimum. One way to think

of it is that you do a search for negative infinity in the search tree. So, you

started the root. And you just keep following left child pointers until you

run out, until you hit a null. And whatever the last key that you visit has

to be the smallest key of the tree, right? Because, think about it, suppose you

started the root. Supposed that the root was not the minimum, then where is the

minimum got to be, It's got to be in the left sub-tree so you follow the left

child pointer and then you just repeat the argument. If you haven't

already found the minimum, where it's got to be with respect to current place,

it's got to be in the left sub tree and you just iterate until you can't go to the left

any further. So for example, in our running search tree. You'll notice that if

we just keep following left child pointers, we'll start at the three, we'll

go to the one, we'll try to go left from the one. We'll hit a null pointer and

we'll return one and one is indeed the minimum key in this tree. Now, given that

we've gone over how to compute the minimum, no prizes to guess how we compute

the maximum. Of course, if we want to compute the maximum instead of following

left child pointers we follow right child pointers by symmetric reasoning as

guaranteed upon the largest key in the tree. It's like searching for the key plus

infinity. Alright. So what about computing the predecessor? So remember this means

you're given key in the tree, in the element of the tree and you want to find

the next smallest element so for example the predecessor of the three is two. The

predecessor of the two in this tree is the one. The predecessor of the five is the

four. The predecessor of the four is the three. So, here I'll be a little hand

wavy just in the interest of getting through all of the operations in

reasonable amount of time but let me just point out that there is one really easy

case and then there is one slightly trickier case. So the easy case. Is

when the node with the key k has a non-empty left sub tree. If that's the

case, then what you want is simply the biggest element in this node left sub

tree. So, I'll leave it for you to prove formally that this is indeed the

correct way to compute predecessors for keys that do have a non-empty left sub

tree, let's just verify in our example by going through the trees that have a

left sub tree and checking this is in fact what we want. Now, if you look at it,

there's actually only two nodes that have a non-empty left sub tree. The three has a

non-empty left sub tree and indeed the largest key in the left sub tree three is

the two and that is the predecessor of the three so that worked out fine. And then

the other node with a non-empty left subtree is the five and it's left subtree is simply the element four

of course the maximum of that tree is also four. And then you'll notice that is

indeed the predecessor of five in this entire search tree. So, the trickier case

is what happens if you know the key with no left subtree at all. Okay. So, what are

you going to do if you not in the easy case, Well, given at this node with

key k, you only have three pointers and by assumption, the left one is null so that's

not going to get you anywhere, now, the right childpointer if you think about it

is totally pointless for computing the predecessor. Remember, the predecessor

is going to be a key less than the given key k. The right subtree by definition of a

search tree only has keys that are bigger than k. So, it stands for reason to find

the predecessor we got to follow the parent pointer. Maybe in fact more than

one parent pointer so to motivate exactly how we're going to follow parent pointers,

let's look at a couple of examples in our favorite search tree here on the right.

So, let's start with a node two. So, we know we got to follow a parent

pointer. When we follow to this parent pointer, we get to one and boom, one in

fact is two's predecessor in this tree so that was really easy to computer two's

predecessor. It seemed that all we have to do is follow the parent pointer. So, for

another example though which think about the node four. Now, four when we follow

which parent pointer, we get to five and. Five is not 4's predecessor, it's 4's

successor. What we wanted a key that is less than where we started, we follow the

parent pointer and it was bigger. But, if we follow one more parent pointer, then we

get to the three. So, from the two we needed to follow one parent pointer, from

the four we needed to follow two parent pointers. But the point is, you just need

to follow parent pointers until you get to a node with key smaller than your own. And

at that point you can stop and that's guaranteed to be the predecessor. So,

hopefully, you would find this intuitive. I should say, I have definitely not

formally proved that this works and that is a good exercise for those of you that

want to have a deeper understanding of search trees and this magical search tree

property and all of the structure that it grants you. The other thing I should

mention is another way to interpret the, the terminating criteria. So what I've

said is you stop your search of parent pointers as soon as you get to through

smaller than yours If you think it about a little bit, you'll realize you'll get to

a key smaller than yours, the very first time you take a left turn. So the very

first time that you go from a right child to it's parent. Look at the example, when

we started from two, we took a left turn, right? We went from upper link going

leftward To it's a right child of one, and that's when we got to the predecessor in

just one step. By contrast when we started from the four, our first step was to the

right. So, we got to a node that was bigger than where we started for

five is four's left child which is going to be smaller than five. But the first

time we took a left turn on the next step, we got to a node that is not only smaller

than five but actually smaller from four, smaller from the starting point. So, in

fact, you're going to see a key smaller than your starting point at very first

time, you take a left turn, the very first time you go from a node to a parent and in

fact, that node is that parent's right child. So this is another statement which

I think is intuitive but which formally is not totally obvious. And again I encourage

you to think carefully about why these two descriptions of the terminating criteria

are exactly the same so it doesn't matter if you stop when you first find a key

smaller than your starting point. It doesn't matter if you first stop when you

follow a parent pointer that goes from a node that's the right child of a node.

Either way you're going to stop at exactly the same time so I encourage you to think

about why those are the exact same stopping condition. A couple of other

details if you start from the unique node that has no predecessor at all, you'll

never going to trigger this terminating condition so for example if you start from

the node one in the search tree, not only is the left subtree empty which says

you're suppose to start traversing parent pointers but then when you traverse a

parent pointer, you only go to the right. You never turn left and that's because

there is no predecessor so that's how you detect that you're at the minimum of a

search tree. And then of course if you wanted to be the successor of the key

instead of the predecessor, obviously you just flip left and right through out this

entire description. So that's the high level explanation of all of these

different ordering operations, minimum and maximum predecessor and successor work in

a search tree. Let me ask you the same question I asked you when we talked about

search in insertion. How long that these operations take in the worst case? Well,

the answer is the same as it was before. It's proportional to the height of the

tree and the explanation is exactly the same as it was before. So to understand

the dependence on the height was just focused on the maximum operation that has

the state within the question. The other three operations, the running time is

proportional to the height in the worst case for exactly the same reasons. So,

what is the max operation do when you started the root and you just follow the

right child pointers until you run out them so you hit null. So, you know, that

the running time is going to be no worse in the longest such paths. It's particular

path from the root to essentially a leaf. So instead we're going to have a

running time more than the height of the tree, on the other hand for all you know.

The path from the root to the maximum key might well be the longest one in the tree.

It might be the path that actually determines the height of the search tree.

So, for example in our running unbalanced example, that would be a bad tree for the

minimum operation If you look for the minimum in this tree, then you have to

traverse every single pointer from five all the way down to one. Of course there's

an analogious bad search tree for the maximum operation where the one is the

root and the five is all the way down to the left. Another thing you can do is search

trees which mimics what you can do with sorted arrays is you can print out all of

the keys in the sorted order in linear time with constant time per element.

Obviously, in the sorted array this is trivial. Use your for loop start ing at

the beginning at the array pointing up the keys one at a time and there's a very

elegant recursive implementation for doing the exact same thing in a search tree. And

this is known as an in order traversal of binary search tree. So as always you begin

at the beginning namely at the root of the search tree. And a little bit of notation

of which call, all of the search tree that starts at r's left child t sub l and the

search tree routed at r's right child t Sub r. In our running example of course

the root is three t sub l with correspondent in the search tree

comprising only the elements one and two, t sub r would correspond to the sub-tree

comprising only the elements five and four. Now, remember we want to print out

the keys in increasing order. So in particular, the first key we want to print

out is the smallest of them all. So it's something we definitely don't want to do

is we don't want to first print out the key at the root. For example in our search

tree example, the root's key is three, we don't want to print that out first. We

want to print out the one first. So where is the minimum lie? Well, by the search

tree property, it's got to lie in the left subtree t sub l, So we're just going to

recurse on t Sub l. So by the magic of recursion or if you prefer induction, what

re-cursing on t sub l is going to accomplish is we're going to print out all

of the keys in t sub l in increasing order from smallest to largest. Now that's

pretty cool because t sub l contains exactly the keys that are smaller than the

key of the root. Remember that's the search tree property. Everything bigger

than the root's key has to be in the left sub tree. Everything bigger than the

root's key have to be in its right sub tree. So in our concrete example of this

first recursive call is we're going to print the keys one and then two. And now,

if you think about it it's the perfect time to print out the key at the root,

right? we want to print out all the keys in increasing order we've already done

everything less than the root's key Where re-cursing and on the right hand side will

take you everything bigger in it so in between the two recursive calls, this is

why it's called an in order traversal, that's when we want to print out. R's key.