And next, we're going to talk about the 
analysis of path length in binary trees. 
and, this is an important problem to to 
study, because that''s the quantity that 
we use to predict performance in the 
analysis of the binary search algorithm 
that I talked about before. 
So here's the definition that I gave 
before for a binary tree and the level 
and the depth. 
When we talk about path length what we 
want to compute is the average length of 
a path to a node that's in the tree, say 
an internal node. 
so to do that we compute the total 
internal path length and then dividing 
that by n gives, gives that average cost. 
and so to computer the total you just 
count the number of nodes at each level. 
So at level 1 there's, 
2 nodes, at level 2, there 4, level 3, 
there's 3 4, there's 1, 5 there's 1, and 
you add that all up, 
that's called the internal path length, 
of, a binary tree. 
it's the, a sum over all nodes of length 
of a path from the root to that node or 
the sum of k times the number of at that 
at that, the k. 
for binary trees we also talk about 
external path length and that's just the 
same thing for external nodes. 
so external n, also that's a quantity of 
interest in studying the binary search 
algorithm. 
so these things there is relationships 
among these that are easy to prove it's 
all recursive. 
so and there's a lot of notation to be 
able to talk about these things. so let's 
look at some simple relationships among 
them. 
so we're talking about binary trees and 
we have this size function and just a 
different size function for external 
nodes. 
and then its left and right subtrees 
we'll indicate with tl and tr. 
ipl stands for the internal path length, 
xpl stands for the external path length. 
So that's all the notation, and again, 
these are simple quantities to define as 
I did on the previous slide. 
so here's some recurrsive relationships. 
So one thing is the number of internal 
nodes in a tree is the number of internal 
nodes on the left plus the number of 
internal nodes on the right plus one for 
the root so that's five. 
external nodes, it's just 
the, root is not an external node, 
so the number of external nodes in the 
tree is the number of external nodes on 
the left plus the number of external 
nodes on the right. 
internal path link so this is an 
interesting one. 
If you wanted the internal path length of 
the whole tree you take the internal path 
length on the left, and the internal path 
length on the right, and add those 
together. 
And then, what you are is you're are off 
by one on every single node except the 
root. 
So, if you add, t-1, then you're adding 
this length to all the nodes. 
and so that's a recursive relationship 
for the external path length and for 
internal path length and for external 
path length it's similar. 
external path length on the left, 
external path length on the right, but 
you're off by one for every node because 
you didn't take into account the nodes 
that connect the external node the 
subtree to the root. 
So those are simple but very useful 
recursive relationships so and then, from 
those relationships, 
you can prove easy things, like the 
number of external nodes is equal to the 
number of internal nodes plus one, and 
that's just by induction. 
so just plug in [COUGH] from this formula 
here the number of the external nodes is 
the sum of the external nodes in the two 
parts by the inductive hypothesis that's 
equal to tl+tr+1 and then, using the 
recursive relationship of internal nodes 
we're left with internal nodes plus one. 
there's lots of ways to to prove that. 
here is another one external path length 
is equal to internal path length plus two 
times the number of internal nodes in the 
tree. 
And again, that's inductive right from 
the simple recursive relationships that 
we talked about. 
so and again, there's a lot of ways to 
prove those things, too just using these 
as an exercise for getting used to the 
idea of path length in its relationship 
with the path length in the subtrees to 
the path link in the whole tree that is 
critical to the analysis that we're 
going to do. 
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 a 
probability of one over Catalan numbers 
one over n plus [INAUDIBLE]. 
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 how far are all the nodes from the 
root and far is an average node from the 
root? 
This sort of what we're saying with that. 
so these are the quantities that we're 
going to work with. 
so QNk is the number of trees with N 
nodes and in internal path length k. 
Tn is the number of trees, that's a 
Catalan numbers, 
and accumulated cost is the total 
internal path length path length on all 
trees, so that we get the average by 
dividing the accumulated cost by the 
number of trees. 
that's the, that's the way that we 
compute average values of parametrs. 
So this is for two so in this case both 
of the trees with two nodes have internal 
path length of one so the average so the 
total accumulated internal path length is 
one, the average internal path length is 
one, it's still not, 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 zero to the root, one to the 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=1, there's one tree of size 2 
that has internal path length 1, 
and there is four trees of size 3 that 
have internal path length 3. 
and so and that's [INAUDIBLE] equals 
five. 
So the total, the average internal path 
length is 14/5 is 2.8. 
so that's the figures for three and 
here's the corresponding figures for 
four. 
Total path length in all of these trees 
is 74 and there's 14 of them, so the 
average expected internal path length is 
5.2 in these trees of size four. 
And then, you can take that and say the 
average distance to an internal node, 
divide that by four 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 uh,. 
to make sure that you have a good fix on 
the exact quantities that's you're 
analyzing, 
expected path length of a random binary 
tree. 
so here is the analytic combinatorics 
derivation of this and these are all 
things we've defined so far. 
so the counting GF is just the Ccatalans 
and that's all the information we know 
about the Catalan numbers. 
the cumulative cost generating function 
is sum over all trees, internal path 
length times z to the tress of size. 
and that's also equal to the sum of N sum 
of k, number of path length case and, and 
so forth. 
but, from now on, we're just going to go 
with cumulative counting and we know that 
the average is going to be the 
coefficient of z^N and the q divided by 
the coefficient of z^N and the t. 
The coefficient is z^N and the Q is the 
total internal path length of all trees 
of size N. 
If you divide by that by the number of 
trees of size N, then you get the average 
internal path length. 
so that's the cumulative counting method 
that we're going to use to analyze this 
quantity. 
and so now, what we have to do is analyze 
that cumulative, cumulative cost 
generating function and that's what we'll 
do next. 
so we have the counting GF and we have 
the cumulative GF. 
And we're going to use this recursive 
relationship slightly different but 
pretty similar to the one that we just 
talked about. 
the internal path length of a tree is 
equal to the internal path length of its 
two subtrees plus the number of nodes in 
the two subtrees. 
and so from that definition, we can 
immediately write down this decompostion. 
this first one is for the empty tree and 
this other one is for the root. 
but if we have that function, we look at 
this decomposition, the ipl of t is 
exactly equal to that and the size of t 
is exactly equal to that and so we have 
that that double sum for that cumulative 
cost cumulative cost. 
And that decomposition or looking other 
way that construction, now we can 
rearrange terms. 
and you could see for example that 
ipl(tl)z^tl times z^tr, 
that's Q(z)T(z). 
So, that's one of the terms that we find 
in there. 
and the other ones where these tl's come 
in to effect we get t prime of (z)T of z. 
This formula has those four terms and 
using these two equations, it immediately 
reduces to that simple equation relating 
the counting generating function and the 
cumulative generating function, 
recursive equation that relates those two 
generating function. Extremely simple 
argument, it's actually possible to 
develop this symbolically and we'll talk 
about derivations like that in part two. 
but it's worthwhile having the, the 
explicit decomposition in front of us to 
see how directly we get to the equation 
that matters, which is the generating 
fucntion the equation relating the 
generating functions that we can then 
solve and analyze. 
okay, so just to get it all in one slide, 
I'll put those steps down there. 
So, now we know that Q(z) = 2zT(z) times 
Q of z plus zT prime. 
we know what T and T prime are, 
the only thing we don't know is Q so we 
can solve that for Q. 
And then we can just T of z remember 
that's the, the Catalan and we know what 
T sub N is. 
and t prime is just the derivative of 
that which has two terms in it. 
but there is one thing that simplifies 
calculations a lot, 
1-2zT(z) if you multiply this by 2z, it's 
just square root of 1-4z, so that takes 
care of the denominator. 
So there is a little, still a little bit 
of algebra multiplying these two things 
together but there's lots of 
cancellations, because square root of 
1-4z times square root of 1-4z is just 
1-4z. 
so I'm going to not going to pretend I'm 
going to omit some of the algebra but the 
final result is pretty simple. 
so that's an explicit equation for the 
cumulative counting generating function. 
And what do, what do you need? The 
coefficient of z^N in that is the 
internal path length of all the trees of 
size N. 
and just looking at that, you can see 
that it's going to be 4^N 
next turn, is lower in magnitude. so the 
take all those binary trees as Catalan 
number and add up all their internal path 
length and get 4^N. 
It's surprisingly simple. 
It's not exactly 4^N, but asymptotically, 
it's 4^N. 
And that's why we want to do precise 
asymptotics before, 
because, if you take that and divide it 
by the Catalan, all you're left with is 
n^2 of pi N. 
We divided two huge quantitites, but 
since we were working with preice 
asymptotic results, we get a precise 
answer, average internal path length of a 
random binary tree is N square root of, 
is asymptotic to N square root of pi N. 
And that's a very accurate estimate 
[COUGH] for the average internal path 
length. 
And we could do it, we could get it 
exactly, but doing it asymptotically is 
very compelling, 
because it's a simple and suprising and 
unexpected result. 
so now let's look at the same thing for 
random binary search trees. 
So that, that one kind of explains or 
starts to explain the shape of a Catalan 
tree. 
the nodes go down square root of N which 
in a 10,000 node tree, it goes down a 
100. 
It's a good, pretty good size depth and 
that's the average so it goes down a few 
hundred. 
and what about binary search trees? 
Well, here's the same calculation per 
binary search tree. 
but now we're counting permutations that 
result in a binary search tree with N 
nodes and internal path length k. 
and now it's a little easy because the 
counting factor is N factorial we know 
that. 
but still the accumulated cost is the 
same way, it's just that 
we have to count the number of 
permutations, so in this case, some of 
the trees have internal path length 4, 5 
and 6 as before, but the weighting is 
different. 
So all of these 12 permutations give 
four. 
there's only four of them that give 5, 
that's these four, and the remaining 
eight give 6. 
So the total internal path length of the 
trees that you get from all of the 24 
permutations is 74. 
If you divide that by 24 you get 4.833, 
which is less than what you get for 
Catalan trees, because the balanced ones 
are weighted are more, much more likely. 
That's the same setup and now we can use 
analytic combinatorics in this same way 
to analyze the path length of binary 
search trees and get a comparison 
between, showing us the difference 
between these two models. 
so start as usual, but now we have 
permutations and so our cost is the 
length of the permutation. 
but now when we say ipl, we mean, we 
want, the, it's the ipl of a permutation, 
which doesn't make sense, except if you 
say that the permutation is what we want 
is the internal path length of the BST 
you get from that permutation by 
inserting it in to an initially empty 
tree. 
and again the number of permutations of 
size N is N factorial and that saves us a 
step in the calculations as you'll see. 
and accumulated cost is the total ipl of 
binary search trees built from all 
permutations. 
So now our counting EGF is a simple one, 
that's the, the basic EGF for 
permutations it's just 1/1-z. 
we have an N factorial involved, but 
that's our number of permutations, so 
that cancels out. 
Our cumulative cost EGF it's the same 
symbols as before, except now we have 
permutations not trees and ipl has that 
different meaning. 
and so, to get the expected internal path 
length of a binary search tree built from 
a random permutation, we're going to take 
N factorial of coefficient of z^N in that 
divided by N factorial and those N 
factorials cancel out. 
So, it's just almost, it's treating it as 
an ordinary generating function gives us 
the divide by N factorial for free. 
It's just a little calculation trick does 
those, 
because we're using exponential 
generating functions, which means that we 
divide by N factorial but are probability 
spaces permutations, so we want to divide 
by N factorial, so it serves both 
purposes and saves us the step of 
dividing. 
We just look for the coefficient of z^N 
and see if you. 
So next we'll have to look at developing 
a generating function equation for that 
C(z) using the recursive defintion of the 
binary tree structure according to the 
way that we construct trees. 
so, same basic steps as before, it's just 
that we're going to come up with a 
different equation because we have a 
different structure. 
so again, this is a, just a summary what 
we're after is a, a better equation an 
equation that C(z) has to satisfy. 
and then, we're, what we're going to do 
is use this relationship that we talked 
about before, that gives us all the 
permutations that lead to the same tree. 
and so, that decomposition for but, from 
one, from a permutation P to a 
permutation that ipl of P is and those 
are all the permutations that give rise 
to that and then, i, ipl of P is is, got 
that recursive relationship as before. 
we can express everything there in terms 
of p sub l and p sub r, 
because of this decomposition that we 
already talked about. 
And this one is even simpler than the 
other one, there's just one trick that 
often works with exponential generating 
functions. 
This p l plus p one factorial causes in 
the denominator causes a little 
inconvenience in simplifying this 
formula, 
but we have z to that same quantity. So 
what we do is differentiate to cancel out 
that one factor, 
then you'll see there's a pL+pR factorial 
on the bottom and then we can mix that 
with the binomial coefficient. 
so this is a, a trick that often works 
with exponential generating functions. 
Differentiate, then cancel the pL+pR in 
the binomial coefficient and you're left 
with a pL factorial pR factorial. 
And now you've got a very simple double 
sum that completely decomposes and 
separates the [COUGH] you know, P(z) b or 
of P factorial is just P(z) and p prime 
of z is the one that takes care of 
pl over pl is pl minus one factorial, so 
use this equation. 
and then, again, we get a very simple 
differential equation now for the 
cumulative cost exponential generating 
function for path lengths and BSTs. 
Decomposition is important. It's gotta be 
precise. It's gotta be correct, but once 
you have that decomposition, you 
automatically get a relationship that, 
that b exponential generating function 
for the cumulative cost and the counting 
GF have to satisfy. 
[COUGH] And again, solving for C(z) gives 
just simplifying that subtituting in for 
P(z) gives a very simple equation. 
so recognize that equation? we saw that 
in the first lecture actually. 
that's the equation that came up with 
solving the quicksor recurrence. 
I guess it came up in the generating 
functon lecture pretty much the same 
equation. 
So just with that observation, we solve 
that, because it's a first that in first 
order differential equation that has a 
simple integration factor and was not 
difficult to solve. 
so now we can fit the and summarize the 
analysis of expected length of, in a BST 
built from a random permutation on this 
slide. 
start with the definition of equation for 
the cumulative generating function 
substitute in the construction and the 
decomposition. 
differentiate the simplify substitute the 
further simplification 
and that is a generating function that it 
has the solution 2/(1-z)^2 log of 1/1-z - 
2z/(1-z)^2. 
And those are elementary series that we 
can expand to define the coefficients as 
we did before to show that the average 
internal path length in a binary search 
tree is asymptotic to 2N natural log N. 
So a log N as a factor 
if divided by N log N to the average node 
in a binary search tree square root of N 
in a binary Catalan tree. 
in since the same equation comes up and 
people who've had algorithms courses know 
that there's a bijection between 
quicksort and binary search trees that 
explains this. 
We could have analyzed binary search 
trees just by taking advantage of this 
bijection. 
so, that is 
in quicksort, you have the first entry in 
the permutation as the partitioning 
element and the smaller ones and larger 
ones are mixed and then, after the 
partitioning you do them independently. 
and that's pretty much the same in a 
binary search tree you the first, the 
first one is the root and then you do the 
left and right independently. 
so you can show, that the average 
[UNKNOWN] pairs for the quicksort is 
exactly the average external path length, 
like the BST built from a random 
permutation. 
and that's an interesting bijection to to 
know to take advantage of. 
now, this same approach works for a lot 
of other parameters of trees and there's 
exercises to compute the number of leaves 
of trees and other things like that in 
the text. 
for finding the height of trees, it's 
much more intricate, it's a different 
approach, because it doesn't break down 
really as well. 
and that, but that's an interesting 
problem, because it's a natural thing to 
want to know what's the furthest node 
from the root in a tree that tells us 
more information about the shape of the 
tree. 
so the height derivation is described in 
the text. 
And actually for both, for both binary 
search trees and trees height was an open 
problem for quite a while. 
so just to summarize what we know about 
the shapes of these two different tree 
structures. 
we looked at random binary trees and, and 
binary search trees built from a random 
permutation. 
those are typical shape of those trees 
the average path length, that's the 
average distance to a node in a random 
tree, for binary trees, the square root 
of p N, for BSTs from random permutation, 
that's two natural log N. 
And again in, in the book there's some 
description of, of both of these 
derivations that are quite intricate. 
the height now is known for random binary 
trees to be twice that average. 
and for random BSTs, it's a little more 
than twice. 
It's a constant times natural log N, 
where the constant is about 4.31. 
and again there's lots of things that you 
might want to study about trees and I've 
only, I've only really talked in detail 
about path length. 
but you can find plenty of examples in 
the book and that show that the same 
approach works for many other tree 
parameters as well and I certainly don't 
have time to talk about all, all of them 
in this lecture. 
That's a summary of the study of path 
length and trees.