Homework 3 : Operations on Binary Trees

For this assignment you will implement a number of methods for working with binary trees. A project shell with a graphical user interface has been provided for you: you will plug your methods into this shell, and use the shell to test your methods.

The following screen shots show what the program can do and how it should behave. When run, the program creates and displays a randomly constructed binary tree of 15 values. In addition, the program has a user interface to allow the user to execute a number of operations on the binary tree:

The user can type in a value, and the program will find a path that gives the sequence of left-right turns from the root to take to reach the value, and also the values that are encountered on the way to the sought-after value. If there are duplicate values in the tree, the path to the first value found is what is returned.

The user can type in a level and the program will show all values at the level in the tree. The root is at level 0, and the children of the root are at level 1, and so on.

The user can enter a value and the program will find all descendants of that value in the tree. A node is considered to be its own descendant, and any child of a descendant of a node is a descendant of the node. Thus every node is a descendant of the root, and the the descendants of a leaf consist of only the leaf. If there are duplicate values in the tree, the descendants of the first node found are returned.

The user can click on a button to see all the leaves in the binary tree.

Download the project code skeleton and complete the following methods:

    static Node buildRandomTree(int size)
    {
        
    }
    

The buildRandomTree(int size) method builds a random tree with the given number of values. The values of the tree should be randomly generated nonnegative integers less than 100. You must use a recursive insert method to randomly insert a value into an existing binary tree when you are building the tree.

    static boolean 
    getPath(Node tree, int value,  LinkedList valuesOnPath, 
                                   LinkedList turns)
    {
       
       
    } 
    

This method will return the list of left-right turns that lead to the given value, as well as the sequences of values on that path. Turn is an enumeration value defined in the project skeleton code file. The method returns false if value is not found in the tree.

    static void getValuesAtLevel(Node tree, int level, List values)
    {
       
    }    
    

This method returns a list of all values at that are in the tree at the given level.

     static void getLeaves(Node tree, List leaves)
    {
       
    }
    

This method returns a list of all leaves in the tree.

     static boolean getAllDescendants(Node tree, int value, List values)
    {
        
    }
    

This method returns in values the list of all descendants of the given value. The method returns false if the value is not found in the tree.

You may write additional methods if you need them, and then you can call those methods.

Due Date

Thursday of Week 6. Be sure you know how to do these problems before the quiz on Thursday.