## CS 2401 Assignment #8

Due Date: Monday, April 18 or Tuesday, April 19, depending on the day of your lab.

Objective: The goal of this assignment is to practice the use of binary search trees.

Assignment: Write several recursive methods related to trees:

• a method that, given a binary search tree, returns its smallest element;
• a method that, given a binary search tree, returns its largest element;
• a method that, given a binary search tree, returns the total number of elements in the tree;
• a method that, given a binary search tree, returns its height;
• a method that, given an element and a binary search tree, checks whether this element belongs to this tree;
• a method that, given an element and a binary search tree, adds this element to the tree (no balancing is needed).

Main idea. For example, to find a given element in a given tree, we do the following. First, we check whether the tree is empty. If the tree is empty, then the given element is not there, otherwise we compare the given element with the root of the tree:

• if the element is equal to the root, we return "true";
• if the element is smaller than the root, we search in the left subtree;
• if the element is larger than the root, we search in the right subtree.

For extra credit: write similar recursive methods that compute other characteristics of the tree: e.g., total number of elements which are positive or which are even, etc.