Composite Pattern Iterator without recursion

Question

Has anyone written or thought about writing an iterator for a composite (tree) structure without using recursion? If so can you share your ideas? Thks

Edit: I was thinking of Java for lang.

Answer 1

Traversing a tree without recursion is simple enough. Assuming a binary tree, each node presumably has three references to other nodes. Left child, right child and parent. So assuming a depth-first left to right iteration order, you follow the left-child references in a while-lop (pseudocode while current.left-child != null, current = current.left-child) if there is no left-child, you try the right child. If there is no right child either, you go up until you find a right-child (while current.right-child == null, current = current.parent)

You haven't specified a language, but since you want to avoid recursion, I'm going to assume it's an imperative language of some sort, and then the above should be possible.

In short, your iterator must hold a reference to the current node, and some information about which way it's travelling.