I am self learning lisp and thought a nice non-trivial program would be to write a set of standard tree insertion and manipulation routines. I figured it could be done with CONS but wanted to try it with a structure. 

I put together one version that worked:

```
(defstruct treenode data left right)

(defun tree-insert ( value tree )
"Insert data into tree"
(if tree
  (if (< value (treenode-data tree))
       (setf (treenode-left tree) (tree-insert value (treenode-left tree)))
       (setf (treenode-right tree) (tree-insert value (treenode-right tree))))
  (setf tree (make-treenode :data value)))
tree)

```

which rebuilt the tree at every step which seemed computationally inefficient. By inefficient, I mean that I have to use setf every time I do another level of recursion. So I wanted to try a scheme that passed the tree by reference rather than by value so I could make assignments in the subroutine that inserts into a tree.

I cobbled the following together, which does not work (but give me credit for having comments):

```
(defstruct treenode data left right)

(defun tree-insert ( value tree )
"Insert data value into tree, using pass by reference.

value  A datum to insert, in this version has to be a number.
tree   The tree passed as a symbol."  

(setq tval (symbol-value tree))
(if (eq tval nil)
  (set tree (make-treenode :data value))          ; Empty tree. Place data here.
  (if (< value (treenode-data tval))              ; Non-empty node.  Decide which subtree for insert.
      (tree-insert value (treenode-left tval))    ; Left side
      (tree-insert value (treenode-right tval)))) ; Right side.  This is a stable sort.   
nil)

? (setf tr nil)
NIL
? (tree-insert 10 'tr)
NIL
? tr
#S(TREENODE :DATA 10 :LEFT NIL :RIGHT NIL)
? 

```

The initial insert works fine. Passing a symbol the (set tree ...) correctly inserts the structure with left and right porinters nil. 

Of course, the problem that follows is that on the recursive call to tree-insert I am not passing a symbol. 

That is the hangup. I haven't found a way to refer to a structure slot as a symbol that I can then pass to tree-insert.

I've been looking around for a couple of days and found this interesting comment about the defstruct macro: "defstruct not only defines an access function for each slot, but also arranges for setf to work properly on such access functions, defines a predicate named name-p, defines a constructor function named make-name, and defines a copier function named copy-name. All names of automatically created functions are interned in whatever package is current at the time the defstruct form is processed (see *package*). Also, all such functions may be declared inline at the discretion of the implementation to improve efficiency; if you do not want some function declared inline, follow the defstruct form with a notinline declaration to override any automatic inline declaration."

So, what could I do to do the magic that setf does? I know I can do assignments to slots with setf, but I haven't gotten setf to work in a function due to lexical scope rules. Maybe like adding automatic functions to allow symbol generating, like (treenode-data-symbol tr)?

Of course, lisp programmers have dealt with binary trees since before my first PDP-8/L. What's the lispy way to do this?

This is an edited question. User Rainer Joswig gave a very fast and concise response. I learned a lot from the example he gave. I was interested in the issue of modifying the tree directly rather than using a return value from a function.

From the comments I've seen here, and the one answer by Rainer Joswig, should I draw the conclusion that the pointer manipulation is computationally low in cost, and that the best lisp approach is to use a function that returns a tree rather than relying on an approach of modifying the argument?