1

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.

Vidhya
  • 61
  • 1
  • 6

2 Answers2

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.

jalf
  • 243,077
  • 51
  • 345
  • 550
  • Agree with the binary tree traversal, but I didnt want to assume a binary tree. – Vidhya Feb 06 '09 at 15:02
  • 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 – jalf Feb 06 '09 at 15:43
0

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.

Community
  • 1
  • 1
GETah
  • 20,922
  • 7
  • 61
  • 103