Walking a tree and executing a callback when visiting each node can be done in three ways:
- Pre-order, executing the callback before descending
- In-order, which executes the callback after descending left, but before descending into the right subtree
- Post-order, where the callback is executed after descending
Each of these traversal strategies yields a different order of tree elements, with in-order producing a sorted output, while pre- and post-order create a more structurally oriented sorting. For our users, the in-order walk will provide the best experience, since it also lets them reason better regarding the expected outcome, and, if displayed in a list, it's easier to navigate.
While implementing this walk is very easy to do recursively, providing an iterator is more user-friendly (just like the lists in the previous chapter) and it enables a number of added functions, such as map() and filter(). However, this implementation has to be iterative, which makes...