CODEWITHSUNDEEP
schemebinary-tree
TPerson
TPerson

Reputation: 41

Function for determining if set of values in 1 binary search tree are equal to another in scheme

I'm attempting to write a function that checks if all the values in one binary search tree all appear in another with the function (bst-set-equal), such that (bst-set-equal? '(1 (5 () (6 () ()))) '(5 (1 () ())(6 () ()))) returns true. However, the function I've written is returning false, and I have been unable to determine why. I hadn't run into any issues with bst-subset? when I tested it, but that could very well be the issue, as the setup of bst-set-equal seems to make sense.

(define (bst-element? item bst-tree)
  (cond ((null? bst-tree)#f)
        ((equal? item (bst-value bst-tree))#t)
        ((bst-element? item (bst-left bst-tree)))
        (else (bst-element? item (bst-right bst-tree)))))

(define (bst-subset? bst1 bst2)
  (cond ((null? bst1)#t)
        ((bst-element? (bst-value bst1)bst2)
         (and (bst-subset? (bst-left bst1)(bst-left bst2))
              (bst-subset? (bst-right bst1)(bst-right bst2))))
        (else #f)))

(define (bst-set-equal? bst1 bst2)
  (cond ((and (bst-subset? bst1 bst2)
              (bst-subset? bst2 bst1))#t)
        (else #f)))

Upvotes: 1

Views: 397

Answers (1)

Renzo
Renzo

Reputation: 27434

The problem is in the function bst-subset?, when the test (bst-element? (bst-value bst1) bst2) returns true: you check if the left subtree of bst1 is contained in the left substree of bst2, but it could be contained in the whole tree bst2 (and analogously for the rigth subtrees). Moreover, you do not check for emptyness of bst2, which can lead to an error.

You could change the function in this way:

(define (bst-subset? bst1 bst2)
  (cond ((null? bst1) #t)
        ((null? bst2) #f)
        (else (and (bst-element? (bst-value bst1) bst2)
                   (bst-subset? (bst-left bst1) bst2)
                   (bst-subset? (bst-right bst1) bst2)))))

Note also that you could simplify the definition of bst-set-equal? by eliminating the redundant cond, in this way:

(define (bst-set-equal? bst1 bst2)
  (and (bst-subset? bst1 bst2)
       (bst-subset? bst2 bst1)))

and, similarly, you could simplify the definition of bst-element? as well, for instance in this way:

(define (bst-element? item bst-tree)
  (if (null? bst-tree)
      #f
      (or (= item (bst-value bst-tree))
          (bst-element? item (bst-left bst-tree))
          (bst-element? item (bst-right bst-tree)))))

Upvotes: 1

Related Questions