4 ms·
I feel like programming an iterator like this akin to a state machine is just not that convenient or trivial, though. Below is pseudo-Java. class InOrderTree
by trealira 1y ago
I feel like programming an iterator like this akin to a state machine is just not that convenient or trivial, though. Below is pseudo-Java.
class InOrderTreeIterator {
Stack stack;
TreeNode cursor;
InOrderTreeIterator(TreeNode root) {
cursor = root;
s = new Stack;
}
bool hasNext() {
return cursor != null || !stack.empty();
}
TreeNode next() {
if (cursor != null) {
while (cursor.left != null) {
stack.push(cursor);
cursor = cursor.left;
}
} else if (!stack.empty()) {
cursor = stack.pop();
} else {
throw new NoSuchElementException();
}
TreeNode ret = cursor;
cursor = cursor.right
return ret;
}
}
- munificent 1y agoIt's much easier if the language has built-in support for generators. Here's an in-order tree iterator in Dart: Iterable<TreeNode> inOrder(TreeNode node) sync* { if (node.left != null) yield* inOrder(node.left!); yield node; if (node.right != null) yield* inOrder(node.right!); }
- trealira 1y agoYeah, if it has built-in support for generators, it basically makes the state machine implicit for you, which is nice and convenient; it's like going from having to manage your own stack call stack to using a programming language that just allows function calls and recursion.