CSCI H343 Data Structures Fall 2023

Lab 4: Next Prev Binary Tree

Background and Overview

This lab is a stepping stone for the Segment Intersection Project.

The lab is to finish a BinaryTree class that implements the Sequence and ReverseSequence interfaces. These interfaces are defined in terms of iterators, Iterator and ReverseIterator. Traversing according to the Sequence should provide an inorder traversal. Traversing according to the ReverseSequence should provide a backwards inorder traversal.

Support Code and Submission

Problem Set

Problem 1: Tree Traversal

Part 1: Helper functions

The first step is to implement next and previous methods in the Node class (which is nested inside the BinaryTree class). We recommend that you start by implementing the following helper functions in the Node class, which come in handy when trying to move forwards or backwards within the binary tree:

    public Node first();
    public Node last();
    public Node nextAncestor();
    public Node prevAncestor();

Part 2: Next and Previous

Once the above helper functions are complete, it is straightforward to implement methods that return the next and previous nodes according to an inorder traversal:

    public Node next();
    public Node previous();

Part 3: Iter

You can now move on to finish the implementation of the Iter class (which is nested inside the BinaryTree class) by filling in:

These methods are 1-liners.

Problem 2: Testing

Write test cases in BinaryTreeTest.java with one method named test(). This method should thoroughly test the BinaryTree class.

Test and debug your own code from Problem 1 locally and then submit both your code and your test cases to Autograder for grading.

The Autograder will apply your tests to buggy implementations of the BinaryTree class. You receive 1 point for each bug detected. The Autograder will also apply your tests to a correct implementation to rule out false positives.