Okay, so here's our first problem.

We have a random binary tree so that's a binary tree where all tree shapes

are equally likely with probability one over, catalan numbers one over N plus.

What's the average path length of a random binary tree?

That's some kind of description of the tree shapes that we saw.

How far are all the nodes from the root and

how far is an average node from the root?

That's sort of what we're saying with that.

So, these are the quantities that we're going to work with.

So Q and K is the number of trees with N nodes and internal path link of K.

TN is the number of trees that's the cattlen numbers and

to accumulate costs is the total internal path link on all trees.

So that we get the average by dividing the cumulated cost by the number of trees.

That's the way that we compute average values of parameters.

So this is for two, so in this case, both of the trees

with two nodes have internal path length of 1.

So the total accumulated mature path length is 1,

the average internal path length is 1, that's still not so interesting.

Now this is a little more interesting.

So there's five trees with three nodes.

Four of them have internal path length, three.

0 to the root, one to one below.

And two more to the next one.

So that's three.

Four of them have that structure.

One of them has internal path length.

Two the nodes are both just one from the root.

So Q32 equals one.

Is one tree size two has an internal path length to one and

there's four trees to size three that have internal path length three.

And so, that's a bug, it's t3=5, so

the average internal path length is 14 over 5, it's 2.8.

So that's the figures for three and here's the corresponding figures for four.

Total path lengths in all of these trees is 74 and there's 14 of them.

So the average expected internal path length

is 5.2 in this trees at size 4.

And then you can take that and say that the average distance to an internal node,

divide that by 4 again to get about how far a node is from the root.

So that's the quantities that we're after.

It's always good to do small cases like this to

make sure that you have a good fix on the exact quantities that you're analyzing.