Tree-walking algorithms: Incremental postorder walk of an N-ary tree

devblogs.microsoft.com

48 points·GordonS··3 comments

Full series:

* Tree-walking algorithms: Incrementally enumerating leaf nodes of an N-ary tree - https://devblogs.microsoft.com/oldnewthing/20200106-00/?p=10...

* Tree-walking algorithms: Incrementally performing a preorder walk of an N-ary tree - https://devblogs.microsoft.com/oldnewthing/20200107-00/?p=10...

* Tree-walking algorithms: Incrementally performing a postorder walk of an N-ary tree - https://devblogs.microsoft.com/oldnewthing/20200108-00/?p=10...

* Tree-walking algorithms: Incrementally performing an inorder walk of a binary tree - https://devblogs.microsoft.com/oldnewthing/20200109-00/?p=10...

I've used "Modified Preorder Tree Traversal" as a method for storing tree-structured/hierarchical data a few times. (Threaded 'forums', 'Folder'-type management/curation of RSS feeds (to churn out OPML, for example)

Walking the tree like this provides some mind-bogglingly easy ways of presenting 'branches/nodes' of the tree and their descendants, as well as the pathway to a node.

It required each item to have a 'left' and 'right' value, along with efficiently (as possible) updating those values when the structure changes.

I've always thought there must be many more ways this could be used these days, for things we haven't thought of yet.

In reading Knuth's volume one a few years ago, I was surprised by the threaded tree structure he presents. Gives easy ways to do stack free traversal of a tree.

I confess there is no good reason this surprised me. But it did. I share your thought that there are probably more uses for this than I've seen. I'll modify the thought and say I just assume they are getting used and I don't know if the doors directly. (I'll note that you can view a DOM tree as threaded, do I have seen stack free traversal used. Just not often.)

Reply on news.ycombinator.com