LISP - Postorder Traversal

Lisp - Post-order Tree Traversal

Tree traversal is a fundamental algorithm in computer science. This chapter demonstrates how to perform a post-order traversal on a binary tree represented in Common Lisp.

Post-order Traversal Explained

In a post-order traversal, we process the nodes of a binary tree in a specific sequence:

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

This “left-right-root” pattern is applied recursively to every node in the tree.

Consider the following binary tree:

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

A post-order traversal would visit the nodes in this order:

D → E → B → F → G → C → A

This traversal order is useful in scenarios like calculating the size of directories in a file system or deleting nodes in a tree, as you process children before the parent.

Tree Representation in Lisp

There are multiple ways to represent trees in Lisp. A classic, simple approach is using nested lists, but a more robust and modern method is to use defstruct.

Modern Approach: Using defstruct

Using defstruct creates a dedicated data structure for our tree nodes. This makes the code clearer, less error-prone, and more efficient than using plain lists.

;; Define a structure for a binary tree node
(defstruct node
  value  ; The data at this node
  left   ; The left child (another node or nil)
  right) ; The right child (another node or nil)

;; Construct our example tree using the node structure
(defvar *my-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))))

(print *my-tree*)

Here, make-node creates an instance of our node structure, and accessors like node-value, node-left, and node-right are automatically created for us.

Example: Post-order Traversal Implementation

The implementation is a direct translation of the recursive algorithm.

main.lisp

;; Define a structure for a binary tree node
(defstruct node
  value
  left
  right)

;; The traversal function
(defun post-order-traversal (tree-node)
  ;; Only proceed if the current node is not nil
  (when tree-node
    ;; 1. Traverse the left subtree
    (post-order-traversal (node-left tree-node))

    ;; 2. Traverse the right subtree
    (post-order-traversal (node-right tree-node))

    ;; 3. Visit the root node (in this case, print its value)
    (format t "~a " (node-value tree-node))))

;; Construct our example tree
(defvar *my-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))))

;; Execute the traversal and print a newline at the end
(post-order-traversal *my-tree*)
(terpri)

Output

When you load and run this code, it will produce the expected post-order sequence:

D E B F G C A

Explanation

• defun: Defines the function post-order-traversal.
• when tree-node: This is the base case for the recursion. If the function is called on an empty child (nil), it does nothing and returns.
• node-left and node-right: These are the accessor functions automatically generated by defstruct. They are used to retrieve the left and right children of a node.
• node-value: This accessor retrieves the data stored at the current node.
• Recursion: The function calls itself on the left and right children. This process continues until it reaches the leaves of the tree (nodes with nil children), at which point it starts printing values as the recursion unwinds.

Testing the Traversal

To properly test such a function, you can modify it to return a list of values instead of printing them. This allows for automated verification.

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

;; Test assertion
(assert (equal (post-order-collect *my-tree*)
               '(D E B F G C A)))

(format t "Test passed!~%")