UMM CSci 2101 Labs, Spring 2005: Lab 8

CSci 2101 Data Structures: Lab 8

Problem 1: recursive methods of a tree

Download the most recent version of the IntBST.java, IntNode.java, and the testing program written in class from this page.

Write the following recursive methods:

countOdd to count all the odd numbers in the tree.
min to find the smallest element in the tree. Hint: it's a binary search tree, so you know where the smallest element is.
countLeaves to count all the leaves in the tree.
allOdd which returns true if all the elements of the tree are odd and false otherwise.
printDecreasing to print the tree elements in decreasing order. Hint: which of the three traversal methods should you use as a starting point?

Recall that in order to write recursive methods for a tree you have to write recursive methods of the nodes. Please test your methods thoroughly and submit your test cases.

Problem 2: recursive methods of linked lists

Use the linked lists implementation here. Recursion in linked lists is similar to that in a tree: you need to write the recursive method in the Node class and call it in LinkedList class on the first node.

Write the following recursive methods:

length to find the length of the list.
sum to find the sum of all data in the list.
Extra credit. hasEvenNumberElements returns true if the list has an even number of elements and false otherwise. Don't use the length() method.

This is a lab from CSci 2101 course.