©2007 Felleisen, Proulx, et. al.

3  Methods for Complex Class Hierarchies; Libraries

Portfolio Problems

Pair Programming Assignment

Binary Search Trees

3.1  Problem

Here is an HtDP data definition:

;; A Binary Search Tree (BST) is one of
;; --- empty
;; --- Node

;; A Node is (make-node Number BST BST)
(define-struct node (value left right))

;; we expect the value to be a whole number

The BST (the binary search tree) has the property that all values in the left sub-tree are smaller than the value of the node, and all values of the right subtree are larger than the value of the node. (We will not allow the same number to be a value of more than one node in the tree.)

  1. Define the Java class hierarchy that represents a BST.

  2. Design the method that counts the number of Nodes in a BST. (Method name count)

  3. Design the method that adds the values of all nodes in the BST. (Method name totalValue)

  4. Design the method that determines whether a given number is one of the node values in the BST. (Method name contains)

  5. Design the method that inserts a new node with the given value into the right place in the BST. If there already exists a node with the given value, the method produces the BST that looks the same as the original one. (Method name insert)

  6. Design the method that produces the smallest number recorded in the BST. (Method name first)

  7. Design the method that removes the node with the smallest value from the BST. The method produces a new BST. (Method name rest)

Last modified: Wednesday, October 3rd, 2007 8:37:58am