LISP - Search Tree

Lisp - Searching in Trees

Trees are a fundamental data structure, and in Lisp, they are naturally represented using lists. This tutorial covers modern, idiomatic approaches to searching for a value within a tree structure.

Representing Trees with Lists

A common and simple way to represent trees in Lisp is with nested lists. We’ll consider two forms:

• Binary Tree: Each node is a list of the form (value left-subtree right-subtree). An empty subtree is represented by NIL.
• Generic Tree: Each node is a list of the form (value child1 child2 ... childN).

Example Definitions

;; A binary tree: (1 (2 nil (3 nil nil)) (4 (5 nil nil) nil))
(defparameter *binary-tree*
  '(1 (2 nil (3 nil nil))
      (4 (5 nil nil) nil)))

;; A generic tree: (A (B (C) (D)) (E (F) (G)))
(defparameter *generic-tree*
  '(A (B (C) (D))
      (E (F) (G))))

;; Note: Using `*earmuffs*` is a convention for naming global special variables.

A Modern, Functional Search Algorithm

We can write a single, elegant Depth-First Search (DFS) function that works for both tree representations. A functional approach using some is more concise and idiomatic than a manual loop.

main.lisp

(defun tree-contains-p (target tree)
  "Searches for TARGET in a generic list-based TREE using DFS.
  Returns T if found, otherwise NIL."
  (when tree
    (let ((node-value (first tree))
          (children (rest tree)))
      (or (eql node-value target)
          (some (lambda (child) (tree-contains-p target child))
                children)))))

;; --- Search the binary tree ---
(format t "Binary tree contains 3: ~a~%" (tree-contains-p 3 *binary-tree*))
(format t "Binary tree contains 6: ~a~%" (tree-contains-p 6 *binary-tree*))

;; --- Search the generic tree ---
(format t "Generic tree contains 'G: ~a~%" (tree-contains-p 'G *generic-tree*))
(format t "Generic tree contains 'Z: ~a~%" (tree-contains-p 'Z *generic-tree*))

Output

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

Binary tree contains 3: T
Binary tree contains 6: NIL
Generic tree contains 'G: T
Generic tree contains 'Z: NIL

Explanation of the tree-contains-p function

• (when tree ...): The base case for the recursion. If the tree (or subtree) is NIL, it’s empty, so we stop and return NIL.
• (let ...): We locally bind the node’s value (first tree) and its children (rest tree). This improves readability.
• (or ...): This is the core of the logic. It first checks if the current node-value is the target.
• (some ...): If the target is not found at the current node, some applies the search function recursively to each child. some conveniently stops and returns a true value as soon as any recursive call finds the target, making the search efficient.

Beyond Lists: A More Robust Approach with defstruct

While list-based trees are great for learning, real-world applications often benefit from a more structured and robust representation using defstruct or defclass. defstruct automatically creates a constructor, accessors, and a type for your nodes.

Example with defstruct

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

;; Create a tree using the structure
(let ((struct-tree (make-bnode :value 'A
                               :left (make-bnode :value 'B')
                               :right (make-bnode :value 'C'))))

  ;; Access data with auto-generated functions
  (format t "Root value of struct tree: ~a~%" (bnode-value struct-tree))
  (format t "Left child's value: ~a~%" (bnode-value (bnode-left struct-tree))))

;; Rewriting the search function for this struct would be more robust and often faster.