Wellesley College
CS230: Data Structures in Java
Spring 2026

Homework 9, Part A: Guitar

You all have been working so hard. We’ve decided to skip this part of the homework :).


Homework 9, Part B: Tree Recursion

Learning Goals

Tasks

First, create a BlueJ project with the following starter code.

BTNode.java:

import java.util.LinkedList;

public class BTNode<T> {
    protected T element;
    protected BTNode<T> left, right;

    public BTNode(T elmt) {
        element = elmt;
        left = right = null;
    }

    public T getElement() { 
        return element; 
    }

    public void setElement(T element)
    { this.element = element; }

    public BTNode<T> getLeft() { 
        return left; 
    }

    public void setLeft(BTNode<T> left) { 
        this.left = left; 
    }

    public BTNode<T> getRight() { 
        return right; 
    }

    public void setRight(BTNode<T> right) {
        this.right = right; 
    }

    public BTNode<T> find(T target) {
        BTNode<T> result = null;

        if (element.equals(target)) {
            result = this;
        } else {
            if (left != null)
                result = left.find(target);
            if (result == null && right != null)
                result = right.find(target);
        }

        return result;
    }

    public int count() {
        int result = 1;

        if (left != null)
            result = result + left.count();

        if (right != null)
            result = result + right.count();

        return result;
    }

BSTNode.java:

public class BSTNode<T extends Comparable<T>> extends BTNode<T> {

    public BSTNode(T element) {
        super(element);
    }

    public void add(T item) {
        if (item.compareTo(element) < 0) {
            if (left == null)
                left = new BSTNode(item);
            else //  Add recursively 
                ((BSTNode) left).add(item);
        } else { //  item >= element, go right
            if (right == null)
                right = new BSTNode (item);
            else //  Add recursively 
                ((BSTNode) right).add (item);
        }
    }

    public BSTNode<T> find(T target) {
        if (target.compareTo(element) == 0)
            return this;
            
        // Since left and right are defined as BTNodes in the parent class,
        // we cast them to BSTNodes here so we can call compareTo
        BSTNode<T> l = (BSTNode<T>) left;
        BSTNode<T> r = (BSTNode<T>) right;
        
        if (target.compareTo(element) < 0 && l != null) {
            return l.find(target);
        }
            
        if (r != null) {
            return r.find(target);
        }
        
        return null;
    }
}

Next, implement the following instance methods:

  1. Implement public int countLeaves() in the BTNode class. This method should return an integer counting the number of leaves in tree.
  2. Implement public int countNodesAtLevel(int level) in the BTNode class. This method should return the number of nodes at a given level in the tree. In this method, we’ll say that level 0 represents the root.
  3. Implement public LinkedList<T> collectOnlyChildren() in the BTNode class. This method should return a list of all elements T that belong to nodes that have no siblings.
  4. Implement public boolean everyParentGreaterThanChildren() in the BSTNode class. This method should return true if the element stored at every node is larger than the elements stored at its immediate left and right children.

Please test your code as you go, putting your test in a driver class called Driver.java.


Submission Checklist