LISP - Modifying Tree

Lisp - Modifying Tree Structures

Building on our understanding of trees, this chapter focuses on modifying them: searching for nodes, adding new ones, and deleting existing ones. We will work with a general tree, where a node can have any number of children. Our approach will be functional, meaning our modification functions will return a new, updated tree rather than changing the original one in place.

Representing a General Tree

We’ll represent a general tree node as a list where the first element is the node’s value and the rest of the list contains its children (subtrees).

;; Example Tree: A is the root, with children B and C.
;; B has children D and E. C has one child F.
(defvar *my-general-tree* '(A (B (D) (E)) (C (F))))

;; --- Helper Functions for Abstraction ---
(defun node-value (tree)
  "Gets the value of the root node of a tree."
  (first tree))

(defun node-children (tree)
  "Gets the list of children of the root node."
  (rest tree))

1. Searching for a Node

To search for a node, we check the current node’s value. If it’s not a match, we recursively search in each of its children. The some function is perfect here, as it stops and returns T as soon as any of the recursive calls finds a match.

(defun search-node (tree node-to-find)
  "Searches for a node in the tree. Returns T if found, otherwise NIL."
  (when tree
    (if (eql (node-value tree) node-to-find)
        t ; Found it at the current node
        (some #'(lambda (subtree) (search-node subtree node-to-find))
              (node-children tree)))))

2. Adding a Node

Our insert-node function will add a new child node to a specified parent. It returns a new tree with the modification. If the parent isn’t found, it returns the original tree.

(defun insert-node (tree parent-value new-child-node)
  "Non-destructively inserts a new child to a parent node."
  (if (null tree)
      nil
      (if (eql (node-value tree) parent-value)
          ;; Found the parent, construct a new node with the new child added.
          (cons (node-value tree) (cons new-child-node (node-children tree)))
          ;; Otherwise, recurse on children and rebuild the tree.
          (cons (node-value tree)
                (mapcar #'(lambda (subtree)
                            (insert-node subtree parent-value new-child-node))
                        (node-children tree))))))

3. Deleting a Node

Deleting a node is more complex. Our function will build a new tree that excludes the specified node and its entire subtree. The original tutorial’s implementation was flawed, as it left a NIL placeholder. A correct functional approach rebuilds the parent’s child list without the deleted node.

(defun delete-node (tree node-to-delete)
  "Non-destructively deletes a node and its subtree."
  (if (null tree)
      nil
      (let* ((current-value (node-value tree))
             (children (node-children tree))
             ;; Step 1: Recursively process children to handle deletions deeper in the tree.
             (processed-children
               (mapcar #'(lambda (child) (delete-node child node-to-delete)) children))
             ;; Step 2: Filter out any children that became the node-to-delete.
             (filtered-children
               (remove-if #'(lambda (child) (eql (node-value child) node-to-delete))
                          processed-children)))
        ;; Step 3: Return nil if the current node is the one to be deleted, otherwise reconstruct it.
        (if (eql current-value node-to-delete)
            nil
            (cons current-value filtered-children)))))

Complete Example (main.lisp)

;; Define the tree and helpers (as shown above)
(defvar *my-general-tree* '(A (B (D) (E)) (C (F))))

;; --- Initial State ---
(format t "Original Tree: ~s~%" *my-general-tree*)

;; --- Searching ---
(format t "Searching for 'D': ~a~%" (search-node *my-general-tree* 'D)) ; ==> T
(format t "Searching for 'Z': ~a~%~%" (search-node *my-general-tree* 'Z)) ; ==> NIL

;; --- Inserting ---
(format t "Inserting '(G)' under 'B'...~%")
(setf *my-general-tree* (insert-node *my-general-tree* 'B '(G)))
(format t "Tree after insert: ~s~%~%" *my-general-tree*)

;; --- Deleting ---
(format t "Deleting node 'D'...~%")
(setf *my-general-tree* (delete-node *my-general-tree* 'D))
(format t "Tree after delete: ~s~%" *my-general-tree*)

Output

Original Tree: (A (B (D) (E)) (C (F)))
Searching for 'D': T
Searching for 'Z': NIL

Inserting '(G)' under 'B'...
Tree after insert: (A (B (G) (D) (E)) (C (F)))

Deleting node 'D'...
Tree after delete: (A (B (G) (E)) (C (F)))

Best Practices and Further Learning

• Functional Purity: Notice how our functions don’t modify the input tree. They return a new one. This prevents side effects and makes code easier to reason about, especially in complex or concurrent programs.
• Edge Cases: Our functions handle null trees gracefully. A robust implementation would also consider what to do when a parent node for insertion doesn’t exist.
• Performance: For very large and frequently modified trees, this functional approach can be inefficient due to the amount of list copying. In such cases, developers might use destructive operations carefully or choose entirely different data structures (like hash tables or CLOS objects).
• Project Idea: Try to model a simple file system. Implement functions like find-path, mkdir (insert), and rm (delete).