Complexity of a cutting operation on a list of binary trees

Consider a list of full binary trees of heights $(h_0, h_1, ldots, h_{n-1})$ where a tree with a single leaf is deemed to have height 0.

The list has the property that the height of the tree when going through the list is, at first strictly increasing, and then strictly decreasing, i.e $$exists k, 0 leq k < n, ~forall i, (1 leq i leq k implies h_{i-1} < h_{i}) wedge (k leq i < n implies h_{i} > h_{i+1})$$

Examples of list of heights that have this property

()
(4)
(0, 1, 5) 
(0, 1, 3, 2, 1) 
(3, 0)

Examples of lists that do not have this property

(3, 3)
(3, 4, 2, 3)

The total number of leaves in this list $sum_{i=0}^n 2^{h_i}$ so, in the worse case, the length of the list is bounded by $2 log_2 l$ if $l$ is the number of leaves.

We define the "take" operation on a list in pseudocode as follow

take quantity forest :
   result = []
   while quantity > 0 and forest not empty:  
      if 2^(forest.head.height) < quantity:
         forest = forest.tail
         insert = front
         while result not empty and result.front.height = insert.height
              insert = merge(insert, result.head)
              result = result.tail
         result = cons(insert, result)
         quantity = quantity - 2^(front.height)
      else:
         forest = cons(forest.head.left, cons(forest.head.right, forest.tail))    
   return result

It’s not too hard to convince oneself that this take operation preserves the property of being increasing then decreasing of the list (although the invariant can be temporarily violated in the loop).

It’s a bit less obvious than the list returned by the procedure also has this property, but it still seems true.

Much less obvious is the worst-case complexity of the operation as a function of $l$, the number of leaves. The inner while looks like it could introduce some quadratic $mathcal{O}(log^2 l)$ complexity, but it is not obvious that this is actually the case.

So what is the worse case complexity of this procedure?