treeschemebinary-search-treeracketracket-student-languages

Work with binary search trees in Racket


I want to create a binary search tree in Racket. The structure for tree looks like this:

(define-struct tree-node (left right root))

Now I want to add these numbers in the tree:

(define ex-list (list 1 4 6 2 7 8))

My Code for the insert procedure:

(define (insert-in-tree list tree) 
  (cond
    [(empty? tree) 
      (insert-in-tree (cons (second list) (rest (rest list))) 
                      (make-tree-node empty empty (first list)))]
    [(empty? list) 
      tree]
    [(> (first list) (tree-node-root tree)) 
      (insert-in-tree (cons (second list) (rest (rest list))) 
                      (make-tree-node 
                          (tree-node-left tree) 
                          (make-tree-node empty empty (first list)) 
                          (tree-node-root tree)))]
    [(< (first list) (tree-node-root tree)) 
      (insert-in-tree (cons (second list) (rest (rest list))) 
                      (make-tree-node 
                          (make-tree-node empty empty (first list)) 
                          (tree-node-right tree) 
                          (tree-node-root tree)))]
    [(= (first list) (tree-node-root tree)) 
      (insert-in-tree (cons (second list) (rest (rest list))) tree)]
    [else tree]))

What is my idea of the code:

My Problem: When the tree is just the 1 and the procedure adds the 4 its added as a new root element in the right side. When I then add the 6 it will replace the 4 but it should add a new node for the 6.

I know that this version of code is not working because in the case when the list is just one element this code won't work.

The level of code is Intermediate Student


Solution

  • This:

    (cons (second list) (rest (rest list))) 
    

    is a very strange way to write (rest list), which also ensures an error if list is shorter than two elements.

    Changing that, we notice that it will still cause an error for empty lists; so the clause handling this eventuality must be moved to the top

    (define (insert-in-tree list tree)
      (cond
        [ (empty? list)
          tree ]
        [ (empty? tree)
          (insert-in-tree (rest list)
                          (make-tree-node empty empty (first list))) ]
        [ (> (first list) (tree-node-root tree))
          (insert-in-tree (rest list)
                          (make-tree-node
        ........
    

    At least now it doesn't cause an error:

    > (insert-in-tree (list 1 2 3) empty)
    (make-tree-node '() (make-tree-node '() '() 3) 1)
    > (insert-in-tree (list 1 2 3 4 3 5) empty)
    (make-tree-node '() (make-tree-node '() '() 5) 1)
    > 
    

    But scratch all that, your approach is all wrong. Your code mixes up two essentially separate issues: enumerating list elements, and inserting an element into a tree.

    Separate your concerns. Each task deserves its own, dedicated function. Writing it that way will make it easy for you to combine the two tasks, by making small alterations in the list enumeration function, to make use of the insertion function.

    The insertion function will implement the comparison logic, and make use of ... the insertion function, to insert into a branch if need be, since the branches are trees, themselves.