Let T be a (possibly improper) binary tree with n nodes, and let D be the sum of the depths of all the external nodes of T. Describe a configuration for T such that D is W(n²). Such a tree would be the worst case for the asymptotic running time of Algorithm height1 (Code Fragment 7.6).

Code Fragment 7.6: A C++ implementation of the function height1.

The C++ implementation of this algorithm is shown in Code Fragment 7.6. We assume that Iterator is the iterator class for PositionList. Given such an iterator q, we can access the associated position as *q.

int height1(const Tree& T) { int h = 0;

PositionList nodes = T.positions(); // list of all nodes

for (Iterator q = nodes.begin(); q != nodes.end(); ++q) { if (q−>isExternal())

h = max(h, depth(T, *q)); // get max depth among leaves

}r

eturn h;

}