5 ms·
Couldn't you just do this with a regular for loop and a few datatypes/functions? (This pseudocode is an Elm/Haskell/Rust/TypeScript-inspired abomination, but pr
by pseudocomposer 1y ago
Couldn't you just do this with a regular for loop and a few datatypes/functions? (This pseudocode is an Elm/Haskell/Rust/TypeScript-inspired abomination, but pretty portable to any language...)
type Node = { value: Any, left: Node, right: Node }
type Direction = Left | Right
type TreePosition = { root: Node, currentNode: Node = root, position: Direction[] = [] }
# Implementation left as an exercise but should be obvious and run in O(1), I believe. Returns Nothing when we're out of nodes.
function nextPosition(position: TreePosition): Option<TreePosition>
# The tree you want to iterate through
const myTree: Node = ...
# The loop
for(let position: TreePosition? = TreePosition(root: myTree); position != Nothing; position = nextPosition(position) {
node = position!.currentNode
# Your loop code
}
I'd argue this doesn't belong as a language-level feature, but maybe an API/stdlib-level feature.
- xxs 1y agoIndeed, I don't see any need to have a tree as a language primitive along with a traversal function (iterator). Tree traversal is not really different than iterating over a vector/list. E.g. even java has stuff like: TreeSet.forEach(consumerRef) or for(Type val : tree) doStuffWith(val)
- HelloNurse 1y agoTrees are an insignificant middle ground between lists (which, by the way, are degenerate trees) and general iterators (on general object graphs, or not even materialized).