Binary tree insert.

Ok I have one last problem...
I have a binary tree like this....

(question1 (question2 (question4 (answ3) (answ4) ) (question5 (answ5) (answ6) ) ) (question3 (answ1) (answ2) ) )

                    question1
                    /       \
           question2        question3
          /        \         /      \
  question4  question5    answ1     answ2
   /     \    /      \   
answ3 answ4 answ5   answ6

yes goes left and no goes right
I have created a second tree that looks like this....

(newQuestion (answ3)(newans))

          newQuestion
           /       \
      answ3      newAns

So i have traversed my tree and found the answer 'answ3'. Now i have added a new question and a new answer.
I want to insert that newQuestion to the leaf where ans3 is/was.

I have found the answ3 so i was thinking of doing a search through my tree for that leaf. Then i need to replace that leaf with my new node which i am stumped at.
So it's essentially an insert function but I don't know how to go about it. Can I step through the tree and then cons or append it when i reach the right spot?

Thanks for the help.

just to clarify this will be the new tree...

                    question1
                    /       \
           question2        question3
          /        \         /      \
  question4  question5    answ1     answ2
   /     \     /      \   
newQues answ4 answ5   answ6
  /   \
answ3  newAns

You could do a doubly linked list - that way finding the parent of the leaf becomes trivial, but another, perhaps simpler way, if all nodes are unique would be to have a hash-map alongisde the list, which would contain all nodes in the format key = child, value = parent.

Wvxvw assumes you found answ3 only. It seems like you have done search prior to your insert? If you changed your search function to include the parent the insert would be trivial. You could return the parent as a second return value in your search with (values ans ans-parent) and do search for update with multiple-value-bind.. OR you could make a function to traverse the tree again to return the parent (assuming the extra search has little performance impact).No need to do messy doubly linked lists unless. You absolutely need to

You can do this:

(setq *print-circle* t)
(defvar *list* (list 1 2 3 nil))
(setf (nth (1- (length *list*)) *list*) *list*)

With this you can have links for parents in childs.
// That's a pity that last isn't setf-able (... by the standard - yeah I know about defsetf).

And with the same thing you can replace the element in a list.

(defvar *test* (list 1 2 3))
(setf (nth 2 *test*) '(a b c))

Your structure uses too many conses. Use (parent left . right) [i.e., (parent . (left . right))] rather than (parent (left) (right)) [i.e., (parent . ((left . nil) . ((right . nil))))], then you can tell whether, say, "left", is a question or an answer using CONSP. Your original tree looks like

(question1 (question2 (question4 answ3 . answ4) question5 answ5 . answ6)
 question3 answ1 . answ2)

and what you're asking for is

(subst '(newQuestion answ3 . newAns) 'answ3 <original>)