LISP - Inorder Traversal

Tree Traversal in Common Lisp

Trees are a fundamental data structure in computer science. In Lisp, they can be represented in various ways. This tutorial explores the classic in-order traversal algorithm for a binary tree, demonstrating both a traditional list-based approach and a more robust, modern struct-based implementation.

Understanding In-Order Traversal

In-order traversal is a depth-first algorithm that visits the nodes of a binary tree in a specific sequence. The algorithm is defined recursively:

1. 1. Traverse the left subtree.
2. 2. Visit the root node.
3. 3. Traverse the right subtree.

For a binary search tree, an in-order traversal visits the nodes in ascending sorted order. Consider the following tree:

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

The in-order traversal for this tree would produce the sequence: D, B, E, A, F, C, G.

Approach 1: Classic List-Based Representation

A traditional way to represent a tree in Lisp is using nested lists, where each list or sublist represents a node and its children: (node-value left-subtree right-subtree).

;; A tree represented as a list of lists.
(defvar *my-list-tree* '(A (B (D nil nil) (E nil nil)) (C (F nil nil) (G nil nil))))

In this structure, we use accessor functions like car (or first) for the value, cadr (or second) for the left subtree, and caddr (or third) for the right subtree.

Code: inorder-list-traversal

(defun inorder-list-traversal (tree)
  "Performs an in-order traversal of a list-based tree, printing node values."
  (when tree
    (inorder-list-traversal (second tree)) ; Traverse left
    (print (first tree))                    ; Visit root
    (inorder-list-traversal (third tree))))  ; Traverse right

;; --- Usage ---
(inorder-list-traversal *my-list-tree*)

Output

D
B
E
A
F
C
G

Approach 2 (Best Practice): Using defstruct

While list-based trees are simple, they are not very robust. A modern, recommended approach is to use defstruct (or defclass) to define a clear structure for a node. This makes the code more readable, type-safe, and maintainable.

(defstruct node
  value
  left
  right)

defstruct automatically creates a constructor make-node and accessors node-value, node-left, and node-right.

Code: Building and Traversing a Struct-based Tree

;; --- Define a testable traversal function that returns a list ---
(defun inorder-traversal (tree)
  "Performs an in-order traversal of a struct-based tree, returning a list of values."
  (when tree
    (append (inorder-traversal (node-left tree))
            (list (node-value tree))
            (inorder-traversal (node-right tree)))))

;; --- Create the tree using our struct ---
(defvar *my-struct-tree*
  (make-node :value 'A
             :left (make-node :value 'B
                            :left (make-node :value 'D)
                            :right (make-node :value 'E'))
             :right (make-node :value 'C
                             :left (make-node :value 'F)
                             :right (make-node :value 'G'))))

;; --- Usage and Testing ---
(let ((result (inorder-traversal *my-struct-tree*)))
  (print result)
  ;; Best practice: add a test to verify the result
  (assert (equal result '(D B E A F C G))))

Output

(D B E A F C G)

Further Exploration: Pre-order and Post-order

By rearranging the three basic steps, you can implement other standard traversals:

• Pre-order Traversal (Root, Left, Right): Useful for creating a copy of the tree. Sequence: A, B, D, E, C, F, G.
• Post-order Traversal (Left, Right, Root): Useful for deleting a tree, as you delete children before the parent. Sequence: D, E, B, F, G, C, A.