Confused about binary search trees (Scheme)

Question

I have a problem that I need to complete:

We can represent a nonempty binary tree by list (root left_subtree right_subtree) and the empty tree by the empty list. Each binary search tree with integer labels can be considered representing a set of integers. Write a function which, given a set of integers S as a bst and an integer x, returns both the set of all the integers less than x and that of all the integers greater than x as bst’s. Use a pair rather than a list to represent the resulting sets.

I'm very new to Scheme. I've built trees using SML as well as prolog, but can't seem to get a hold of what I need to do for Scheme. Could anyone help me out and guide me towards this goal? Is my tree suppose to just look like this?

(list value left right)

WorBlux WorBlux · Accepted Answer · 2013-12-07T04:06:42

Yes, that's one way to define a tree. Just so long as you make a proper ADT and use it consistently, it shouldn't matter after you've defined it.

(define (make-tree root left right) 
  (list root left right))

(define (right tree)
 (caddr tree))

(define (left tree)
 (cadr tree))

(define (root tree)
 (car tree))

(define (empty-tree? tree)
  (null? tree))

(define empty-tree '())

(define (leaf? tree)
 (and (empty-tree? (left tree)) (empty-tree? right tree)))

(define (split-tree-at tree x)
 (let ((less ...)
       (more ...))     
  (cons less more))

(define (in-tree-below-x tree x) ;;assuming a sorted tree
  (cond ((empty-tree? tree) (empty-tree))
        ((>= (root tree) x)
         (in-tree-below (left tree) x))
        (else (make-tree (root tree) 
                         (left tree)
                         (in-tree-below-x (right tree) x)))))

Confused about binary search trees (Scheme)

1 Answers