Unusual stack overflow when inserting nodes in binary tree

Question

CLISP Version: 2.49

Leaf Node

(value (NIL) (NIL))

Non-Leaf Node

(value (value (NIL) (NIL)) (NIL))

Code ("format" for debug only)

; (nil) means NULL
(defun binary-insert (root obj <) 
(if (null (cdr root))
    (progn 
        (format t "In Null [~A] => " root) 
        (setf (car root) obj) 
        (format t "mid [~A] => " root) 
        (setf (cdr root) '((nil) (nil))) 
        (format t "[~A]~%" root))
    (if (funcall < obj (car root))
        (progn 
            (format t "In Left [~A] => " root) 
            (binary-insert (nth 1 root) obj <) 
            (format t "[~A]~%" root)) ; Left
        (progn 
            (format t "In Right [~A] => " root) 
            (binary-insert (nth 2 root) obj <) 
            (format t "[~A]~%" root)) ; Right
        )
    )
)

Test

[1]> (load "binary_tree.lisp")
;; Loading file binary_tree.lisp ...
;; Loaded file binary_tree.lisp
T
[2]> (setf *glb-rt* '(NIL))
(NIL)
[3]> (binary-insert *glb-rt* 10 #'<)
In Null [(NIL)] => mid [(10)] => [(10 (NIL) (NIL))]
NIL
[4]> *glb-rt*
(10 (NIL) (NIL))
[5]> (binary-insert *glb-rt* 5 #'<)
In Left [(10 (NIL) (NIL))] => In Null [(NIL)] => mid [(5)] => [
*** - Lisp stack overflow. RESET

It seems the program died after executing

(setf (cdr root) '((NIL) (NIL)))

Thanks....

[Update]

Before (setf (cdr root) '((NIL) (NIL))), the "root" is (5)

Another test

[6]> (setf glb-ls '(5))
(5)
[7]> (setf (cdr glb-ls) '((NIL) (NIL)))
((NIL) (NIL))
[8]> glb-ls
(5 (NIL) (NIL))

Please format your code properly. As it is presented now, it is unreadable. — sds
– sds, Commented Oct 1, 2015 at 11:38

sds · Accepted Answer · 2015-10-01 20:04:01Z

2

This question has been answered in the CLISP FAQ How do I avoid stack overflow?

In your case the very first suggestion works: after

(setq *print-circle* t)

we get

In Left [(10 (NIL) (NIL))] => In Null [(NIL)] => mid [(5)] => [#1=(5 #1#  (NIL))]

i.e., you are mistakenly creating a circular structure.

PS. You now owe me 10 zorkmids :-)

edited Oct 1, 2015 at 20:04

answered Oct 1, 2015 at 14:55

sds

60.5k31 gold badges178 silver badges303 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Cozak Over a year ago

Oh!!! Thanks a lot!!! .........But it is not over i think >..< Why I got a circular list instead of (10 (5 (NIL) (NIL)) (NIL))??? Before (setf (cdr root) '((NIL) (NIL))), the "root" is (5) <blink> I make a test below [6]> (setf glb-ls '(5)) (5) [7]> (setf (cdr glb-ls) '((NIL) (NIL))) ((NIL) (NIL)) [8]> glb-ls (5 (NIL) (NIL)) </blink> PS: Zorkmid..coin O..o ?? I have CNY coins only ╮(╯▽╰)╭

sds Over a year ago

you now need to close this question (which has been answered!) and ask a new question about your bug, but first you need to learn how to indent your code.

Collectives™ on Stack Overflow

Unusual stack overflow when inserting nodes in binary tree

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related