So, the root, which is one, comes first, and then-

>> And then it would have to be four,

cuz it's the one's only child.

And then I guess two and eight come in either order.

>> Yeah, so there's two possibilities for D.

>> So as you saw when the U C San Diego students discussed this problem,

all the four options are valid trees.

You can think about the root node of each of these trees,

you can think about the leaf nodes of each of these trees, and

you notice that they're all satisfying the properties that are required for trees,

and not only that, they're all binary search trees.

And so notice that every node has at most two children and that when we look at

the elements or the values stored in each of these nodes, we always have that

nodes on the left have smaller values than the nodes to the right of them.

So we have four valid options of binary search trees.

But, then, the question is, in what order might we have inserted the elements

in order to get to these very, very different shaped trees that we have here.

So let's start with the first option, option A and

we notice that the root of the tree will have to come first when we insert it.

And that's because when we insert nodes into a binary search tree,

we always insert nodes as leaf nodes, so they don't have any children.

And so if we start out with nothing, our very first element is

going to be the root node because the root is not a child of any other node.

So we know that our first element to go in is going to have to be the number two.

But then the question is what happens next?

And whether there are any constraints that are imposed on us by the shape that

we see already.

And what the learners discussed, and what you might be observing as well,

is that the eight had to have been inserted after the four because it shows

up here as a child of the node four.

And so that means that in our possible orderings,

eight is always going to come after four.

But that means that it could go at the end so then it could have two and then one and

then four and eight.

Or we could have had four and eight be inserted immediately after two and then

the one at the end, or we could have had four inserted and then one and then eight.

And that's okay because the node for one and the nodes for

four and eight really don't interact very much with one another,

and so they could have been inserted in any order into this tree.

All right, so these are the three options that we have for

insertion orders that lead into this shaped binary search tree.

But now let's look at option B and

we notice that we have a slightly similar shaped tree.

As before the root comes first, and as before, we noticed that when

we have a child node, that it had to have been inserted after its parent.

And so that means that we have a constraint of four had to be inserted

after eight.

But as before, there's still some freedom in terms of how we insert one

relative to the nodes four and eight.

And so again, we have the three options that mirrored the collection of

options that we had for option A.

But now we get to something quite different when we look at option C, and

in option C we notice that the shape that we're thinking about is a linear shape.

And so we start at the bottom with the root and the root had to come first, but

then we have other constraints as well.

So we see that the node two had to be inserted after one,

because that's a child of one, but then also four needed to be inserted after two

because it's a child of two, and then also eight needed to be inserted after four,

and so all of a sudden we have completely constrained the insertion order into this

binary search tree because every single node has already been determined.

It's position in the insertion order completely determined, and so the order

in which we inserted elements is exactly one, then two, then four, then eight.

And that's the only way to have inserted them, in order and

in that order, in order to get that path-like tree.

All right.

Last but not least, we've got this tree and

it looks quite different from the other ones that we've thought about.

Still, the root will have to come first when we insert into this tree, but now

notice that the dependencies are that both leaf nodes are children of that node four.

And so both two and eight needed to be inserted after four, which meant that four

had to come right after one, right after the root, in the insertion order,

because we had to have space for two other elements behind it.

But those two other elements, well they could go in whatever order they want

because neither is a child of the other.

And so we have two options for the insertion order,

either two before eight or eight before two.

And now we've gone through all of the options that we were considering and

the take home message of this concept challenge is that the order in which

we put elements into a binary search tree impact the shape, and

what you'll see is that the shape of the binary search tree will have a huge

impact on the performance of operations with that binary search tree.

And so you want to keep that in mind when you're working with this data structure.