I'm a complete newbie to lisp, and I'm going through a tutorial and getting confused. I'm wondering if someone can help me out.

The tutorial is here: http://www.cs.sfu.ca/CC/310/pwfong/Lisp ... rial3.html, and the part I'm having trouble with is this:

Code: Select all

```
(defun BST-remove (B E)
"Remove E from BST B."
(if (BST-empty-p B)
B
(if (bin-tree-leaf-p B)
(BST-leaf-remove B E)
(BST-node-remove B E))))
(defun BST-leaf-remove (L E)
"Remove E from BST leaf L."
(if (= E (bin-tree-leaf-element L))
(make-empty-BST)
L))
(defun BST-node-remove (N E)
"Remove E from BST node N."
(let
((elmt (bin-tree-node-element N))
(left (bin-tree-node-left N))
(right (bin-tree-node-right N)))
(if (<= E elmt)
(if (bin-tree-leaf-p left)
(if (= E (bin-tree-leaf-element left))
right
N)
(make-bin-tree-node elmt (BST-node-remove left E) right))
(if (bin-tree-leaf-p right)
(if (= E (bin-tree-leaf-element right))
left
N)
(make-bin-tree-node elmt left (BST-node-remove right E))))))
```

What I don't understand is this part:

Code: Select all

```
(if (<= E elmt)
(if (bin-tree-leaf-p left)
(if (= E (bin-tree-leaf-element left))
right
N)
```

But why would it return the node in that case? If it just returns the node, then it hasn't removed anything. It failed to remove E from the tree!

Am I right in thinking that E

*must*be either the left leaf or the node above it (or both)? In any case, I fail to see how E is removed.

Can anyone explain this?