Reading material

Pages 178-179.

Additional material

For a strong binary tree with n nodes of maximal height, a call of isBalanced on the root of the tree will result in (n-1)/2 * (n+1)/2 calls of size.

The variable maximum in the pseudo code for the array based implementation binary trees is not needed.

out: the elements of the tree
let col be an empty collection
i = 1
j = 0
while j < size
    loop-inv: col contains the elements with level number smaller than i and 
              col contains j elements
    if tree[i] contains an element
          add the element to the collection col
          increment j
    increment i
return col