Surprisingly elegant code

Late last night I wanted to wrap up binary tree traversal into a generator — that is, rather than having the control flow of the program be specified by the traversal, making a function that yields the next element from the tree each time it is called.

It turned out to be easier than I imagined, requiring only one newish operation: depth-first traversal of the left branch of a node, collecting onto a stack the elements thus traversed. I termed this “enstack-l”.

Assuming that your tree has a btree-root accessor, and that each node has node-l, node-r, and node-elt accessors, the Common Lisp code is simply

(defun btree-generator (btree)
  (let ((stack (list)))
    (labels ((enstack-l (bn)
               (loop for b = bn then (node-l b)
                     while b do
                     (push b stack)))
             (pop-and-process ()
               (let ((bn (pop stack)))
                 (when bn
                   (enstack-l (node-r bn))
                   (node-elt bn)))))
      
      (enstack-l (btree-root btree))
      
      (lambda ()
        (pop-and-process)))))

(If the btree itself is just its topmost element, as it would be for a simple cons tree, the function becomes even simpler.)

Isn't it nice when things are easier than you thought? That while inside the loop alone handles a couple of tests for null.

Posted at 2007-10-14 18:41:33 by Richard • Link to Surprisingly elega…