LISP - Depth First Traversal

Lisp - Tree Traversal: Depth-First Search

A tree is a fundamental hierarchical data structure. Depth-First Search (DFS) is a classic algorithm for traversing or searching a tree. It explores as far as possible along each branch before backtracking. In this tutorial, we’ll implement the three main types of DFS traversal on a binary tree in Common Lisp.

Representing a Binary Tree

A common way to represent a binary tree in Lisp is with nested lists. We will use the format (VALUE LEFT-SUBTREE RIGHT-SUBTREE), where NIL represents an empty subtree.

Let’s define a sample tree that we will use for our examples:

;;      F
;;     / \
;;    B   G
;;   / \   \
;;  A   D   I
;;     / \   /
;;    C   E H

(defvar *my-tree*
  '(F (B (A nil nil)
         (D (C nil nil)
            (E nil nil)))
     (G nil
        (I (H nil nil)
           nil))))

To make our code cleaner, let’s define some helper functions to access the parts of a node.

(defun node-value (node) (first node))
(defun left-child (node) (second node))
(defun right-child (node) (third node))

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

In a pre-order traversal, we visit the current node first, then recursively traverse the left subtree, and finally recursively traverse the right subtree.

Implementation

(defun pre-order-traversal (tree)
  (when tree
    (cons (node-value tree)
          (append (pre-order-traversal (left-child tree))
                  (pre-order-traversal (right-child tree))))))

;; Run the traversal on our tree
(print (pre-order-traversal *my-tree*))

Output

(F B A D C E G I H)

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

In an in-order traversal, we first recursively traverse the left subtree, then visit the current node, and finally recursively traverse the right subtree. For a binary search tree, this traversal visits the nodes in sorted order.

Implementation

(defun in-order-traversal (tree)
  (when tree
    (append (in-order-traversal (left-child tree))
            (list (node-value tree))
            (in-order-traversal (right-child tree)))))

;; Run the traversal on our tree
(print (in-order-traversal *my-tree*))

Output

(A B C D E F G H I)

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

In a post-order traversal, we recursively traverse the left and right subtrees first, and then visit the current node last. This is useful for operations where a node must be processed after its children, such as freeing memory for the nodes.

Implementation

(defun post-order-traversal (tree)
  (when tree
    (append (post-order-traversal (left-child tree))
            (post-order-traversal (right-child tree))
            (list (node-value tree)))))

;; Run the traversal on our tree
(print (post-order-traversal *my-tree*))

Output

(A C E D B H I G F)

Practical Applications

Depth-first search algorithms are foundational in computer science and are used in:

• Topological Sorting: Ordering tasks with dependencies.
• Pathfinding: Finding a path between two nodes in a graph, such as in a maze.
• Compilers: Constructing and processing abstract syntax trees.
• AI: Searching state spaces in game-playing and planning problems.