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 Ω(n²). Such a tree would be the worst case for the asymptotic running time of method heightBad (Code Fragment 8.4).

Transcribed Image Text:

/** Returns the height of the tree. */ 1 private int heightBad() { int h = 0; // works, but quadratic worst-case time for (Positionp: positions()) 5 4 if (isExternal(p)) // only consider leaf positions h = Math.max(h, depth(p)); return h;