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.
2 Answers
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.
answered Feb 6, 2009 at 14:40
Stack Overflow is garbage
250k53 gold badges356 silver badges558 bronze badges
2 Comments
Vidhya
Agree with the binary tree traversal, but I didnt want to assume a binary tree.
Stack Overflow is garbage
Well, it's hard to traverse a tree without making some kind of assumption about its structure. The same approach can be trivially modified for any tree structure. Go through its children, then up to the parent and try the next child node
You might get some inspiration from this SO question: Post order traversal of binary tree without recursion All what you need is to extend the algorithm to non binary trees.
