Programming Language : Racket Objective: Implement a Standard Binary Search Tree

Question

Programming Language: Racket

Objective: Implement a Standard Binary Search Tree which include the following functions:

.

.

.

AT THE MINIMUM, IMPLEMENT ADD AND SEARCH TO THE BINARY SEARCH TREE:

1.) (constructBST)

constructs empty BST

2.) (addToBST BST key value)

Adds a key-value pair to a BST, where key is an integer and value is a string, integer, list, etc...

3.) (searchBST BST key)

Searches for a value based on key. Return key if value is not found for the key. Return key and value if value is found for the key.

.

.

.

IMPLEMENT THESE IF YOU ARE CAPABLE OF DOING SO:

4.) (mapBST BST someFunction)

Maps a BST to a new BST with modified values.The values should be modified by an arbitrary function someFunction

Map means is that you apply the function to all the nodes in the tree

mapBST should leave the input BST as is, and create a new BST with the same "treeshape" and same keys, but with different value in each node (based on   someFunction)

For example: if there's a tree with root node 2, and children 1 and 3 and I call map with the function addOne, it becomes one with root 2, children 3 4

5.) (foldBST BST someFunction)

Folding a BST to a single fold-value

Based on traversal of the tree from leaves to root

The returned fold-value should be produced by user-provided someFunction based on key/value of current node a fold-values return from left and right children

.

.

.

;Test cases, be sure at least a few pass:

(define (addAllKeys k v lfv rfv)
(if (null? k)
0 ; if called with null node, return 0
(+ k lfv rfv)
)
)
(define (minimumKey k v lfv rfv)
(if (null? k)
'()
(if (null? lfv)
k
lfv
)
)
)
(define (flattenTree k v lfv rfv)
(if (null? k)
'()
(append lfv (list k v) rfv)
)
)
(define (concatStringValuesPreOrder k v lfv rfv)
(if (null? k)
""
(string-append v lfv rfv)
)
)
(define (concatStringValuesInOrder k v lfv rfv)
(if (null? k)
""
(string-append lfv v rfv)
)
)

;This is where tests occur and should pass

(searchBST bst 5) ; should return: '(5 "5")

(searchBST bst 6) ; should return: '(6)

(mapBST bst string->number) ; should return: '(3 3 (1 1 () (2 2 () ())) (5 5 () ()))
(foldBST bst addAllKeys ) ; should return: 11
(foldBST bst minimumKey ) ; should return: 1
(foldBST bst flattenTree ) ; should return: '(1 "1" 2 "2" 3 "3" 5 "5")
(foldBST bst concatStringValuesPreOrder ) ; should return: "3125"
(foldBST bst concatStringValuesInOrder ) ; should return: "1235"

.

.

.

It's okay to submit partially completed BST, although a fully functional BST is much appreciated.

NOTE: BST = Binary Search Tree, Implement add and search functions at the minimum for the binary search tree

Explanation / Answer

(struct bst-node (val left right) #:transparent #:mutable) (define (bst-add tree value) (if (null? tree) (bst-node value null null) (let ([x (bst-node-val tree)]) (cond [(= value x) tree] [( value x) (if (null? (bst-node-right tree)) (set-bst-node-right! tree (bst-node value null null)) (bst-add (bst-node-right tree) value))]) tree))) (define (childless? node) (and (null? (bst-node-left node)) (null? (bst-node-right node)))) (define (left-child-only? node) (and (not (null? (bst-node-left node))) (null? (bst-node-right node)))) (define (right-child-only? node) (and (null? (bst-node-left node)) (not (null? (bst-node-right node))))) (define (bst-in? b n) (if (null? b) #f (let ([x (bst-node-val b)]) (cond [(= n x) #t] [( n x) (bst-in? (bst-node-right b) n)])))) (define (bst? b) (define (between? b low high) (or (null? b) (and (bst l) (define (convert l) (cond [(= (length l) 1) (bst-node (first l) null null)] [(= (length l) 2) (if (list? (first l)) (bst-node (second l) (list->bst (first l)) null) (bst-node (first l) null (list->bst (second l)) ))] [(= (length l) 3) (bst-node (second l) (list->bst (first l)) (list->bst (third l)))])) (let ([b (convert l)]) (if (bst? b) b (raise-argument-error 'list->bst "bst?" b))))

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.