How do I delete from a binary search tree in Lisp

Question

How can I delete a node from a BST?

I need an algorithm to do that in Dr. Scheme.

Answer 1

You basically toss the BST you have now, and create a new one sans the element.

You can do this by recursively descending the tree. If your item is less than the root datum, create a BST whose root and greater-than branch is copied from what you have now, but whose less-than branch is the result from a recursive call.

It's very similar to how you add a node, but when you get to the one you were searching for, merge the two BSTs below it and return the result. There are surely existing questions about how to do that already.

Answer 2

Assuming your binary search tree uses straight forward cons cells with content only at the leaves, and assuming you are working on a homework assignment: You can use set-car! or set-cdr! to change the content of a cons cell.