LISP - Binary Tree

Lisp - Implementing a Binary Search Tree

A Binary Search Tree (BST) is a fundamental data structure that enables fast data lookup, insertion, and deletion. It’s a node-based binary tree with the following properties:

• The value in a node’s left child (and all its descendants) is less than or equal to the node’s own value.
• The value in a node’s right child (and all its descendants) is greater than the node’s own value.
• Both the left and right subtrees must also be binary search trees.

This structure allows for efficient searching, as you can eliminate half of the remaining tree at each step, leading to an average time complexity of O(log n).

A Modern Representation with defstruct

While it’s possible to represent a tree using nested lists, a more robust and idiomatic Common Lisp approach is to use defstruct. This creates a dedicated data type for our nodes, complete with a constructor and accessors, leading to more readable and maintainable code.

;; Define the structure for a single node in our BST.
(defstruct bst-node
  (value nil :type number) ; The node's data
  (left  nil :type (or null bst-node)) ; Pointer to the left child
  (right nil :type (or null bst-node)) ; Pointer to the right child
  )

;; `defstruct` automatically gives us:
;; - A constructor: (make-bst-node :value ...)
;; - Accessors: (bst-node-value ...), (bst-node-left ...), etc.
;; - A copier: (copy-bst-node ...)

Core Operations

Inserting a Value

Our insert function will be recursive. It finds the correct position for the new value according to the BST rules and inserts a new node there. It returns the (potentially new) root of the tree.

(defun bst-insert (tree value)
  "Inserts a value into the BST and returns the new tree root."
  (if (null tree)
      (make-bst-node :value value)
      (let ((node-value (bst-node-value tree)))
        (cond
          ((<= value node-value)
           (setf (bst-node-left tree) (bst-insert (bst-node-left tree) value)))
          ((> value node-value)
           (setf (bst-node-right tree) (bst-insert (bst-node-right tree) value))))
        tree)))

Searching for a Value

Searching follows the same logic: at each node, we decide whether to go left, right, or if we’ve found our value.

(defun bst-search (tree value)
  "Searches for a value in the BST. Returns the node if found, otherwise NIL."
  (when tree
    (let ((node-value (bst-node-value tree)))
      (cond
        ((= value node-value) tree)
        ((< value node-value) (bst-search (bst-node-left tree) value))
        ((> value node-value) (bst-search (bst-node-right tree) value))))))

Traversing the Tree

Tree traversal is the process of visiting each node in a specific order. The three most common traversals are In-order, Pre-order, and Post-order.

main.lisp

;; Function for In-order traversal (Left, Node, Right)
;; For a BST, this will print the values in sorted order.
(defun bst-in-order (tree)
  (when tree
    (bst-in-order (bst-node-left tree))
    (format t "~a " (bst-node-value tree))
    (bst-in-order (bst-node-right tree))))

;; Function for Pre-order traversal (Node, Left, Right)
(defun bst-pre-order (tree)
  (when tree
    (format t "~a " (bst-node-value tree))
    (bst-pre-order (bst-node-left tree))
    (bst-pre-order (bst-node-right tree))))

;; --- Putting It All Together ---

;; 1. Create an empty tree
(defvar *my-tree* nil)

;; 2. Insert elements. We use a helper to build from a list.
(dolist (val '(27 14 35 10 19 31 42))
  (setf *my-tree* (bst-insert *my-tree* val)))

;; 3. Perform traversals
(format t "In-order (sorted): ")
(bst-in-order *my-tree*)
(terpri)

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

;; 4. Search for a value
(format t "Searching for 19: ~a~%" (if (bst-search *my-tree* 19) "Found" "Not Found"))
(format t "Searching for 99: ~a~%" (if (bst-search *my-tree* 99) "Found" "Not Found"))

Output

In-order (sorted): 10 14 19 27 31 35 42
Pre-order: 27 14 10 19 35 31 42
Searching for 19: Found
Searching for 99: Not Found

Further Learning

This implementation is a great start. However, in a real-world application, you need to consider a critical issue: tree balance. If you insert sorted data (e.g., 1, 2, 3, 4, 5), this simple BST will degenerate into a linked list, and its performance will drop to O(n).

For production use, you would investigate self-balancing binary search trees, such as AVL trees or Red-Black trees, which perform small rotations during insertion and deletion to keep the tree balanced and guarantee O(log n) performance.