0

I'm trying to build a tree in racket. For the moment I have build a "static" tree just for testing the insert method. It runs down the tree to the correct position but it fails to insert the new node.

This is the tree:

(define bst
  (make-node 4
             (make-node 2 empty 
                        (make-node 3 empty empty))
             (make-node 5 empty
                        (make-node 11 empty 
                                   (make-node 12 empty
                                   (make-node 13 empty empty))))))

The insert method (I left all the debugging prints so it's easy to see what happens and the the tree is correct):

(define (insert ABB val)
  (cond[(empty? ABB)(make-node val empty empty)]
       [(< val (node-val ABB))
        (cond
          [(empty? (node-left ABB))
             (printf "\nEntered here\n")
             (node-left ABB)(make-node val empty empty) ; this doesn't work
             (printf "\nABB node-left: ~a" (node-left ABB))
             (printf "\nABB node-left: ~a" (node-val ABB))]
             [else 
              (printf "\nABB node-left (else): ~a" (node-left ABB))
              (insert ((node-left ABB) val))]
             )
        ]
       [(> val (node-val ABB))
        (cond
          [(empty? (node-right ABB))
             (node-left ABB)(make-node val empty empty) ; this doesn't work
             (printf "\nABB node-val (empty): ~a" (node-val ABB))
             (printf "\nEntered here 2\n")
             (node-right ABB)(make-node val empty empty)
             (printf "\nABB node-r:")])]
         [else 
           (printf "\nABB node-val (else): ~a" (node-val ABB))
           (printf "\nABB node-right (else): ~a" (node-right ABB))
           (insert (node-right ABB) val)])
        ]
       )
  )

After that I'm trying to insert 17:

(insert bst 17)

Printing the tree as a list:

(define (tree->list tree)
  (if (empty? tree)
      empty
      (append (tree->list (node-right tree))
              (cons (node-val tree)
                    (tree->list (node-left tree))))))


(printf "\n\nPrinting tree as list: \n")
(tree->list bst)

Output:

Printing tree as list: 
'(13 12 11 5 4 3 2)

'17' doesn't show up. I can't assign the new node to the left/right field of the current node (ABB points to it). What's the problem here?

5
  • If I understand your code correctly, insert should rebuild the tree from scratch, leaving the original tree, to which bst is bound, unchanged. What does (tree->list (insert bst 17)) show? May 16, 2014 at 13:55
  • Yes, that's correct, I'm building it from scratch. But I want to change the original tree which for some reason seems to fail. I added the output of that operation to the post.
    – loxosceles
    May 16, 2014 at 14:18
  • You do not "change the original" by using a "functional" approach which leaves the original unchanged. You could update the binding of bst to use the new tree by (define bst (insert bst 17)) though May 16, 2014 at 14:34
  • Didn't work, the error message says: module: duplicate definition for identifier in: bst
    – loxosceles
    May 16, 2014 at 14:40
  • ah ... sorry about that. racket does not allow re-defining at top-level. The point is: you don't need it in a "real program". May 16, 2014 at 15:02

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.