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;
      }
  }

Don't iterators necessarily "forget" the structure of the tree? I can see how you can write an iterator to, for example, compute the size of a tree, or generate the set of all variables that occur in an expression tree.

But it's not obvious to me how you'd write a generic iterator that supports something like finding all free variables in an expression tree, or even just express a tree mapping function that constructs a new tree with the same structure (for example, "make all variables in the expression uppercase"). It's been a while since I worked with iterators so correct me if I'm wrong and this is in fact easy with iterators.

With something like Haskell's recursion-schemes library [0] these operations are all just a few lines long, guaranteed to terminate, and don't need to be updated if your data structure changes (for example you add new expression nodes). I'm not aware of any non-functional programming language that can do that. See for example the freeVars function at the bottom of the linked recursion-schemes doc.

[0] https://hackage.haskell.org/package/recursion-schemes-5.2.3

I do think recursion schemes are pretty cool, particularly the idea that a list fold could be generalized to the concept of catamorphisms, which could be mechanically derived upon defining a data structure, because the shape of the recursion that's defined is the same as the shape of the recursion of the data constructors. It makes me realize that programming languages still could be higher-level; what if a programming language automatically derived the equivalent of the "fold" and "map" functions for any recursive data type defined by the programmer?

At the same time, the way it's implemented in Haskell's recursion-schemes library might be hard to wrap one's head around at first, kind of like how the list functions "foldr" and "foldl" are also often confusing to newbies, even though they're like the go-to, default way to make list functions in Haskell.