CODEWITHSUNDEEP
listtreeschemebinary-treebinary-search-tree
Anon
Anon

Reputation: 69

Scheme bst-delete-max

I have to create a function bst-delete-max that takes a binary search tree as a parameter and returns a binary search tree with the node that contains the maximum value removed from the tree. I can't use any helper functions that finds the maximum value (bst-max) or a helper function to delete the node (bst-delete). Therefore I am completely lost on how to approach this problem and how to do anything for it. I know that where ever I would have used bst-max I would just have to write the function for finding the largest max value. But how do I delete it? Any help would be greatly appreciated. Here's what I have so far:

 (define (remove-max bs-tree)
  (cond ((null? bs-tree)
     '())
    ((null? (bst-right bs-tree))
     (bst-value bs-tree)
     (car bs-tree)) ;This is the part I know is wrong. How should I fix it?
    (else (remove-max (bst-right bs-tree)))))

Upvotes: 0

Views: 1026

Answers (1)

Óscar López
Óscar López

Reputation: 236014

There are two possibilities when eliminating the maximum element in a BST: The node is a leaf (in that case we must return null) or the node has a left sub-tree (then we must return it, because we only need to eliminate a single node, not a whole sub-tree).

Note that the node can't have a right sub-tree, otherwise it wouldn't be the maximum element. We can cover all the cases by simply returning the left sub-tree, whatever that is - it might even be null, if we're in a leaf. Also, we must build a new tree as we advance, with the same elements - only the right sub-trees will be different.

Assuming that we have a bst-make procedure that receives a value, a left sub-tree and a right sub-tree as parameters, this is how a possible solution would look like:

(define (remove-max bs-tree)
  (cond ((null? bs-tree)
         '())
        ((null? (bst-right bs-tree))
         (bst-left bs-tree))
        (else
         (bst-make (bst-value bs-tree)
                   (bst-left  bs-tree)                   
                   (remove-max (bst-right bs-tree))))))

Upvotes: 2

Related Questions