Difficulty understanding the tree traversal analysis of height1() of O(n^2) in Data Structure and Algorithms in C++ Michael T. Goodrich 2nd ED

Question

I will try my best summarising and explain as best as i can here. This is about tree traversal algorithms.

A) Class Position

template <typename E> // base element type
class Position<E> { // a node position
public:
    E& operator*(); // get element
    Position parent() const; // get parent
    PositionList children() const; // get node’s children
    bool isRoot() const; // root node?
    bool isExternal() const; // external node?
};

B) Class Tree

template <typename E> // base element type
class Tree<E> {
public: // public types
    class Position; // a node position
    class PositionList; // a list of positions
public: // public functions
    int size() const; // number of nodes
    bool empty() const; // is tree empty?
    Position root() const; // get the root
    PositionList positions() const; // get positions of all nodes. According to author, PositionList is implemented as list<Position>. There's no definition for PositionList nor is there implementation for positions() function shown. Left as an exercise.
};

According to author, the depth() & height1() of a tree can be implemented as below.

int depth(const Tree& T, const Position& p) {    
     if (p.isRoot()) return 0; // root has depth 0     
     else return 1 + depth(T, p.parent());     
}    

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
    }
    return h;
}

Author's excerpt:

Unfortunately, algorithm height1 is not very efficient. Since height1 calls algorithm depth(p) on each external node p of T , the running time of height1 is given by O(n+∑p(1+dp)), where n is the number of nodes of T , dp is the depth of node p, and E is the set of external nodes of T . In the worst case, the sum ∑p(1 + dp) is proportional to n^2.

why n^2 (quadratic)?

I tried couple of samples as shown below:

I tried N=5,6,7,8 and it still doesn't come up to n^2.

Any help here be great. Thanks.

Answer 1

In the worst case, the sum ?p(1 + dp) is proportional to n^2

It should be simpler to understand with a "worst case" scenario. Consider a "skewed" subtree with n/2 nodes arranged linearly, and the last node has n/2 children (which will be the leaf or "external" nodes in this case). The tree would look something like

1
 \
  2
  ...
    \
     n/2
 ______|________
|  |  |  |  |  |
(remaining n/2 nodes)

For each external node, we have the depth as n/2, so calculating it takes O(n/2) ~ O(n) time. And since there are n/2 nodes for which depth gets calculated, the complexity becomes O(n/2 * n/2) ~ O(n^2), which is the worst case complexity mentioned by the author.

Edit:

Here's an illustration of the aforementioned tree for n=10. You can see why each external node would require a O(n/2) ~ O(n) traversal: