the nodes that are traversed in step formula_8 by walking up the "rightmost" path of formula_57 (apart from the last node formula_4) are removed from the "rightmost" path, when formula_60 is added to the tree as a new leaf. these nodes will never be traversed again for all subsequent steps formula_113. therefore, at most formula_114 nodes will be traversed in total.