Iterating a TreeMap

TreeMap implements Iterable<K>. Its iterator keeps the nodes it still has to visit on an explicit stack. It starts by pushing the left spine from the root, which is the root and every left child below it. Each call to next pops a node, pushes the left spine of that node’s right child, and returns the popped node’s key.

Solution

10, 25, 30, 55, 70, 85. The iterator traverses the tree in-order, and an in-order traversal of a binary search tree visits the keys in ascending order. It does not depend on the rotations, because a rotation changes the tree’s shape but not the in-order sequence of its keys.

Solution

A full traversal is $O (n)$ , since each node is pushed and popped once, so next is amortized $O (1)$ . One call can push a whole left spine, so a single next is $O (lo g n)$ in the worst case.

Solution

$O (lo g n)$ . The stack holds at most one node per level of the tree.