LISP - Preorder Traversal

Lisp - Pre-order Tree Traversal

Tree traversal is the process of visiting each node in a tree exactly once. In Lisp, where trees are often represented as lists, we can implement traversal algorithms elegantly using recursion. This tutorial focuses on Pre-order Traversal.

The Pre-order Traversal Algorithm

Pre-order traversal follows a specific sequence: Root -> Left -> Right. This means for any given node, we:

1. Visit the Root node itself.
2. Recursively perform a pre-order traversal of its entire Left subtree.
3. Recursively perform a pre-order traversal of its entire Right subtree.

Consider the following binary tree:

      A
     / \
    B   C
   / \ / \
D  E F  G

A pre-order traversal would visit the nodes in this exact order: A → B → D → E → C → F → G

Implementation: Collecting Nodes

A good practice is to write a traversal function that returns a list of the visited nodes rather than printing them. This separates the traversal logic from the output logic, making the function more reusable.

We will use the list representation (value left-subtree right-subtree) for our binary tree.

main.lisp

;; Define the tree using a global parameter for clarity
(defparameter *my-tree*
  '(A (B (D nil nil) (E nil nil))
      (C (F nil nil) (G nil nil))))

(defun collect-preorder (tree)
  "Performs a pre-order traversal of a binary TREE.
  Returns a list of the node values in traversal order."
  (when tree
    (let ((value (first tree))
          (left (second tree))
          (right (third tree)))
      (cons value ; 1. Root
            (append (collect-preorder left)  ; 2. Left subtree
                    (collect-preorder right) ; 3. Right subtree
             )))))

;; --- Execute and print the result ---
(let ((traversal-result (collect-preorder *my-tree*)))
  (format t "The tree definition is: ~s~%" *my-tree*)
  (format t "Pre-order traversal result: ~s~%" traversal-result))

Output

When you execute the code, it returns the following result:

The tree definition is: (A (B (D NIL NIL) (E NIL NIL)) (C (F NIL NIL) (G NIL NIL)))
Pre-order traversal result: (A B D E C F G)

Explanation

• when tree: This is our base case. If a subtree is nil, the recursion stops and returns nil.
• let: We assign the parts of the node (value, left, right) to local variables for clarity. This avoids repeated calls to first, second, etc.
• cons and append: The result is built by consing the current node’s value onto the appended list of the left and right traversal results. This directly mirrors the Root -> Left -> Right logic.

Performance Consideration and an Alternative

The use of append inside a recursion can be inefficient for very deep or unbalanced trees, as it repeatedly creates new lists. A more performant and idiomatic Lisp approach uses an accumulator with a local helper function.

(defun collect-preorder-efficient (tree)
  "A more performant pre-order traversal using an accumulator."
  (let ((result nil)) ; This will accumulate nodes in reverse order
    (labels ((traverse (subtree)
               (when subtree
                 (push (first subtree) result)
                 (traverse (third subtree))  ; Process right first...
                 (traverse (second subtree))))) ; ...then left
      (traverse tree))
    (nreverse result))) ; Reverse the list at the end to get the correct order

;; (collect-preorder-efficient *my-tree*) would also return (A B D E C F G)

In this version, push is a very fast operation. We traverse right-then-left so that when we nreverse the final list, the left subtree’s elements correctly appear before the right’s. This (push ... (nreverse ...)) pattern is a common and efficient idiom in Lisp for building lists.