We will practicing writing code that interacts with tree structures. This includes binary trees, binary search trees, and other types of trees. The exercises will give you more experience working with reference-based structures.

Course:

• Implement a binary search tree data structure and its recursive operations.

Module:

• To write recursive methods that add to, remove from, or iterate over a tree structure.
• Learning how to iterate over the Nodes in a linked list.
• To write informal tests to verify code that is written.

Getting Started

• TreeOperations - Each of the problems you will be solving are included in this file. You will need to read the documentation for the methods to understand how they should work.
• There are three node classes for different exercises:
  • Node - A tree node that stores integer values.
  • StringNode - A tree node that stores strings.
  • DictionaryNode - A tree node storing word/definition pairs that you might find in a dictionary.
• ProgramTests - This class has a main() method to run tests that verify that your methods from TreeOperations are working correctly. There are also individual methods to test each problem.
• TreeHelpers - This file contains a group of useful methods for creating binary trees in different ways.

The Packages and the Classes:

\f\fWrite a method that nds and returns all elements in internal nodes in a tree. Recall that internal nodes are nodes that have at least one child in the tree. Note: The root can also be an internal node! The method should look like the following: /** Identifies the elements in the internal nodes public ArrayList getInteenalNodesCNode Poet) -[ Test your method by passing it several random trees and printing the list of internal nodes to the Java console. Inter'nal Node elements: [5, 6, 13, 16, 193 \f\fWrite a method that uses loops to nd an element in a binary search tree. Hint: We have already seen how to do this recursively. Try to adapt that solution (without copy pasnganycodeltoalooo The method should look like the following: X** This method uses loops [rather than recursion) public hoolean iterativeConteinsENode root, int element) { Test your method by generating a random tree and searching for elements that are in the tree as well as elements not in the tree. Print the boolean result to the Java console of all searches made. iterativeontains1TJz true iterativeContains(12): false iterativeontainsCln): false iteratiueContains(7): false iterativeontainsil): true iterativeContains(9): true \f\f\f\f\f\f\f\f\f\f