Page "AVL tree" Paragraph 7

Once a node has been found in a balanced tree, the next or previous nodes can be explored in amortized constant time.

Some instances of exploring these " nearby " nodes require traversing up to 2 × log ( n ) links ( particularly when moving from the rightmost leaf of the root's left subtree to the leftmost leaf of the root's right subtree ).

However, exploring all n nodes of the tree in this manner would use each link exactly twice: one traversal to enter the subtree rooted at that node, and another to leave that node's subtree after having explored it.

And since there are n − 1 links in any tree, the amortized cost is found to be 2 ×( n − 1 )/ n, or approximately 2.