BST traverse as higher order function
Is this higher order function any use at all without relying on a side-effect?


The answer to this question is obviously no, since the function returns always nil.


  The general question I'm seeking to explore here is the purity or non-purity of higher order functions in practical use cases (and hence, how to use them well).


I'm not sure to understand what you are looking for, but if you want an example of recursive higher order function on binary trees that returns something (without performing side effects), consider the following one, in which the function gets another parameter that “combine” the results of the visit (assuming that an empty tree is represented with nil and that the function should return nil when an empty tree is passed to it):

(defun inorder-traverse (combine fn bin-tree)
  "in order traversal of a binary tree"
  (when bin-tree
    (funcall combine
             (inorder-traverse combine fn (node-l bin-tree))
             (funcall fn (node-elt bin-tree))
             (inorder-traverse combine fn (node-r bin-tree)))))


for instance:

(defun flatten (bin-tree)
  (inorder-traverse (lambda (x y z) (append x (list y) z))
                    #'identity
                    bin-tree))


returns the list of the leaves of a binary tree in order from left to right; if the tree is a BST, the list is sorted;

(defun reverse-flatten (bin-tree)
  (inorder-traverse (lambda (x y z) (append z (list y) x))
                    #'identity
                    bin-tree))


like the previous one, only in reverse order;

(defun map-tree (fn bin-tree)
  (inorder-traverse (lambda (left el right) (mk-tree el left right))
                    fn
                    bin-tree))


returns a new tree, with the same structure of the input one, and with the elements transformed by the function fn;

(defun my-copy-tree (bin-tree)
  (inorder-traverse (lambda (left el right) (mk-tree el left right))
                     #'identity
                     bin-tree))


makes a copy of a binary tree;

(defun reverse-tree (bin-tree)
  (inorder-traverse (lambda (left el right) (mk-tree el right left))
                    #'identity
                    bin-tree))


a symmetrical copy of a binary tree;

etc.