LISP - Tree

Lisp - Working with Trees

In Lisp, the fundamental data structure, the list, is itself a tree. A list is built from cons cells, each having a car (the value) and a cdr (the pointer to the next cell). This recursive structure makes Lisp exceptionally well-suited for creating and manipulating tree data structures.

Representing Trees with Lists

A common and idiomatic way to represent a general-purpose (N-ary) tree in Lisp is with nested lists. A node is represented as a list where the first element is the node’s data, and the rest of the elements are its children (which are themselves trees).

Consider the following tree:

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

In Lisp, this can be represented elegantly as:

(A (B) (C (E)) (D (F (G) (H))))

Here, A is the root node with three children: B, C, and D. B is a leaf node (no children). C has one child, E. D has one child, F, which in turn has two children, G and H.

Built-in Tree-Related Functions

Common Lisp provides several functions that are particularly useful for working with tree-like list structures.

Function	Description
copy-tree tree	Recursively copies an entire tree of cons cells. Unlike copy-list which only copies the top level, copy-tree creates a completely new structure.
tree-equal x y &key :test	Recursively compares two trees for equality. It checks if the structure is identical and the corresponding elements are equal (using eql by default).
subst new old tree &key :test	substitutes every occurrence of old with new throughout the entire tree. This is a non-destructive function; it returns a new tree.
nsubst new old tree &key :test	The destructive version of subst. It modifies the original tree in place, which can be more memory-efficient but should be used with caution.
sublis alist tree &key :test	Performs multiple substitutions at once based on an association list (alist). Each item in the tree is looked up in the alist, and if found, replaced by its associated value.
nsublis alist tree &key :test	The destructive version of sublis.

Example: Using subst and copy-tree

This example demonstrates how to create a tree, make a deep copy of it, and then substitute a value in the new copy, leaving the original unchanged.

;;; main.lisp

(let* ((original-tree '(A (B) (C (B))))
       (copied-tree (copy-tree original-tree))
       (modified-tree (subst 'X 'B copied-tree)))

  (format t "Original Tree: ~s~%" original-tree)
  (format t "Copied Tree:   ~s~%" copied-tree) ; Still unchanged before nsubst
  (format t "Modified Tree: ~s~%" modified-tree)

  (format t "~%--- Verifying non-destruction ---")
  (format t "~%Is the original tree still the same? ~a~%"
          (tree-equal original-tree '(A (B) (C (B))))))

;; Now let's show the destructive version
(nsubst 'Z 'A copied-tree)
(format t "~%--- After destructive nsubst ---")
(format t "~%The 'copied-tree' is now modified: ~s~%" copied-tree)

Output

Original Tree: (A (B) (C (B)))
Copied Tree:   (A (B) (C (B)))
Modified Tree: (A (X) (C (X)))

--- Verifying non-destruction ---
Is the original tree still the same? T

--- After destructive nsubst ---
The 'copied-tree' is now modified: (Z (B) (C (B)))

Building Your Own Tree Utilities

While Lisp’s built-in functions are powerful, you’ll often define your own helper functions for common tree operations like traversal or searching. Let’s create a small utility set for our list-based tree representation.

Node Accessors

These simple functions provide a clean API for accessing parts of a node.

(defun node-data (node)
  "Returns the data of a tree node."
  (first node))

(defun node-children (node)
  "Returns the list of children of a tree node."
  (rest node))

Tree Traversal

A classic tree operation is traversal. Here is a function that performs a pre-order traversal of a tree, collecting the data from each node into a flat list.

(defun pre-order-traversal (tree)
  "Performs a pre-order traversal of the tree, returning a list of node data."
  (when tree
    (cons (node-data tree)
          (loop for child in (node-children tree)
                append (pre-order-traversal child)))))

Example: Building and Traversing a Tree

Let’s use our helper functions to build and then traverse a sample tree.

;;; main.lisp

;; Helper functions from above
(defun node-data (node) (first node))
(defun node-children (node) (rest node))

(defun pre-order-traversal (tree)
  (when tree
    (cons (node-data tree)
          (loop for child in (node-children tree)
                append (pre-order-traversal child)))))

;; Define our file system tree
(let ((fs-tree '(("/")
                 (("home")
                  (("alice")
                   ("notes.txt")
                   ("work.lisp")))
                 (("etc")
                  ("passwd")
                  ("hosts")))))

  (format t "File System Tree:~%~s~%~%" fs-tree)
  (format t "Data of root node: ~s~%" (node-data fs-tree))
  (format t "Children of root node: ~s~%~%" (node-children fs-tree))

  (let ((traversal-result (pre-order-traversal fs-tree)))
    (format t "Pre-order traversal of all nodes:~%~s~%" traversal-result)))

Output

File System Tree:
(("/" (("home" (("alice" "notes.txt" "work.lisp")))) (("etc" "passwd" "hosts"))))

Data of root node: ("/")
Children of root node: ((("home" (("alice" "notes.txt" "work.lisp")))) (("etc" "passwd" "hosts")))

Pre-order traversal of all nodes:
(("/" (("home" (("alice" "notes.txt" "work.lisp")))) (("etc" "passwd" "hosts"))) ("home" (("alice" "notes.txt" "work.lisp"))) ("alice" "notes.txt" "work.lisp") "notes.txt" "work.lisp" ("etc" "passwd" "hosts") "passwd" "hosts")

Practical Application: Mini-Project

A great use for trees is representing hierarchical data like a file system, a scene graph in a game, or an HTML document. A useful function would be to search this tree for a specific node.

(defun find-node (data tree &key (test #'equal))
  "Recursively searches the tree for a node with the given data."
  (cond
    ;; If the tree is empty, we found nothing.
    ((null tree) nil)
    ;; If the current node's data matches, we found it.
    ((funcall test data (node-data tree)) tree)
    ;; Otherwise, search in the children.
    (t (loop for child in (node-children tree)
             thereis (find-node data child :test test)))))

;; --- Example Usage ---
(let ((my-tree '(A (B (C)) (D))))
  (format t "~&Searching for node 'C' in ~s...~%" my-tree)
  (let ((found (find-node 'C my-tree)))
    (format t "Found subtree: ~s~%" found)))

Output

Searching for node 'C' in (A (B (C)) (D))...
Found subtree: (C)