LISP - Recursive Traversal

Lisp - Recursive Tree Traversal

Lisp’s elegance shines in recursive data processing, and tree traversal is a classic example. A tree is a hierarchical data structure composed of nodes. In this updated tutorial, we’ll explore a modern, robust way to represent and traverse binary trees in Common Lisp, focusing on best practices like data abstraction.

Modern Representation of a Binary Tree

A binary tree is a tree where each node has at most two children, referred to as the left child and the right child. While we can use raw lists, a better practice is to define a clear structure and use accessor functions to interact with it. This separates the structure’s implementation from its use.

We’ll represent a node as a three-element list: (value left-subtree right-subtree). An empty tree or a missing child will be represented by NIL.

; Let's define our tree structure:
(defvar *my-tree* '(A (B (D NIL NIL) (E NIL NIL)) (C (F NIL NIL) (G NIL NIL))))

; Helper functions to abstract the structure
(defun node-value (node)
  "Returns the value of a node."
  (first node))

(defun left-child (node)
  "Returns the left child subtree."
  (second node))

(defun right-child (node)
  "Returns the right child subtree."
  (third node))

Using these helpers makes our code cleaner and less prone to errors if we ever decide to change the underlying tree representation (for example, from a list to a struct or class).

Implementing Tree Traversal Algorithms

There are three primary ways to traverse a binary tree recursively. We’ll implement all three: Pre-order, In-order, and Post-order.

1. Pre-order Traversal (Root, Left, Right)

In pre-order traversal, we process the current node’s value first, then recursively traverse the left subtree, and finally the right subtree.

(defun pre-order-traverse (tree)
  "Performs a pre-order traversal of the tree, printing node values."
  (when tree
    (print (node-value tree))
    (pre-order-traverse (left-child tree))
    (pre-order-traverse (right-child tree))))

2. In-order Traversal (Left, Root, Right)

In-order traversal first recursively traverses the left subtree, then processes the current node’s value, and finally traverses the right subtree. For a binary search tree, this visits nodes in ascending order.

(defun in-order-traverse (tree)
  "Performs an in-order traversal of the tree, printing node values."
  (when tree
    (in-order-traverse (left-child tree))
    (print (node-value tree))
    (in-order-traverse (right-child tree))))

3. Post-order Traversal (Left, Right, Root)

In post-order traversal, we recursively traverse the left and right subtrees first, and finally process the current node’s value. This is useful for tasks like deleting nodes from a tree.

(defun post-order-traverse (tree)
  "Performs a post-order traversal of the tree, printing node values."
  (when tree
    (post-order-traverse (left-child tree))
    (post-order-traverse (right-child tree))
    (print (node-value tree))))

Complete Example (main.lisp)

;;; Modern Binary Tree Traversal in Common Lisp

;; --- Data Definition ---
(defvar *my-tree* '(A (B (D NIL NIL) (E NIL NIL)) (C (F NIL NIL) (G NIL NIL))))

;; --- Data Abstraction (Helper Functions) ---
(defun node-value (node) "Returns the value of a node." (first node))
(defun left-child (node) "Returns the left child subtree." (second node))
(defun right-child (node) "Returns the right child subtree." (third node))

;; --- Traversal Algorithms ---
(defun pre-order-traverse (tree)
  (when tree
    (format t "~a " (node-value tree))
    (pre-order-traverse (left-child tree))
    (pre-order-traverse (right-child tree))))

(defun in-order-traverse (tree)
  (when tree
    (in-order-traverse (left-child tree))
    (format t "~a " (node-value tree))
    (in-order-traverse (right-child tree))))

(defun post-order-traverse (tree)
  (when tree
    (post-order-traverse (left-child tree))
    (post-order-traverse (right-child tree))
    (format t "~a " (node-value tree))))

;; --- Execution ---
(format t "Original Tree:~%~s~%~%" *my-tree*)

(format t "Pre-order Traversal: ")
(pre-order-traverse *my-tree*)
(terpri)

(format t "In-order Traversal:  ")
(in-order-traverse *my-tree*)
(terpri)

(format t "Post-order Traversal: ")
(post-order-traverse *my-tree*)
(terpri)

Output

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

Original Tree:
(A (B (D NIL NIL) (E NIL NIL)) (C (F NIL NIL) (G NIL NIL)))

Pre-order Traversal: A B D E C F G
In-order Traversal:  D B E A F C G
Post-order Traversal: D E B F G C A

Key Concepts and Best Practices

• Data Abstraction: Using functions like node-value and left-child decouples your logic from the specific list structure. This is a core principle of good software engineering.
• Recursion Base Case: The (when tree ...) form (equivalent to (if tree ...) ) provides the essential base case for the recursion. When the node is NIL, the function does nothing and returns, stopping the recursive calls.
• Clarity with destructuring-bind: For even cleaner code, you can use destructuring-bind inside your functions:

  (destructuring-bind (value left right) tree
    ; ... use value, left, right directly
  )

• Further Steps: For more complex applications, consider using DEFSTRUCT or the Common Lisp Object System (DEFCLASS) to define your node. This provides type safety and a more formal structure.