The following file contains an implementation a some functions for a binary sear
ID: 3719648 • Letter: T
Question
The following file contains an implementation a some functions for a binary search tree.
binary-search-tree.rkt (code below)
Implement a function (search value binary-search-tree) to search a binary search tree for a given value. It should return #t (true) if the value is in the tree and #f (false) if not.
Extra credit challenge: Implement a function (delete value binary-search-tree) that removes the given value from the binary search tree. It should return the modified binary search tree.
You must use the code below to answer the question.
#lang racket
;Insert a given number in a binary search tree
; The tree is represented as a list (root left-subtree right-subtree))
; where the left-subtree and right subtree are binary search trees (represented as lists)
; Note that the empty tree is represented by an empty list
(define (insert x binary-search-tree)
{cond
[(empty? binary-search-tree) (list x '() '())]
[else
{let
( [root (first binary-search-tree)]
[left-subtree (first (rest binary-search-tree))]
[right-subtree (first (rest (rest binary-search-tree)))]
)
(cond
[(<= x root) (list root (insert x left-subtree) right-subtree)]
[(> x root) (list root left-subtree (insert x right-subtree))]
)
}
]
}
)
;Build a binary search tree from a list of numbers by inserting each number into the tree
; Note the use of reverse so that the numbers are inserted in the correct order using recursion
(define (build-BST number-list)
{letrec
[ (build (lambda (num-list binary-search-tree)
{cond
[(empty? num-list) binary-search-tree]
[else (insert (first num-list) (build (rest num-list) binary-search-tree))]
}
)
)
]
(build (reverse number-list) '())
}
)
; Find the minimum value in a binary search tree
(define (find-min binary-search-tree)
{cond
[(empty? binary-search-tree) "ERROR: Empty Tree"]
[else
{let
( [root (first binary-search-tree)]
[left-subtree (first (rest binary-search-tree))]
)
(cond
[(empty? left-subtree) root]
[else (find-min left-subtree)]
)
}
]
}
)
Explanation / Answer
int isBST(struct node* node)
{
if (node == NULL)
return 1;
/* false if left is > than node */
if (node->left != NULL && node->left->data > node->data)
return 0;
/* false if right is < than node */
if (node->right != NULL && node->right->data < node->data)
return 0;
/* false if, recursively, the left or right is not a BST */
if (!isBST(node->left) || !isBST(node->right))
return 0;
/* passing all that, it's a BST */
return 1;
}
struct node* insert(struct node* node, int key)
{
/* If the tree is empty, return a new node */
if (node == NULL) return newNode(key);
/* Otherwise, recur down the tree */
if (key < node->key)
node->left = insert(node->left, key);
else
node->right = insert(node->right, key);
/* return the (unchanged) node pointer */
return node;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.