Lab 7🔗

Binary Search Trees! But first ... Binary trees.

Implement a binary tree data structure. It should be Generic in the type of the value contained at each node.

Here are some methods to implement; because the binary tree typically uses "null" to represent an empty tree, these will have to be static.

You will also need to have a generic Linked List. (Copy your existing code, make it generic.)

1. A countNodes method that accepts a binary tree and returns a count of the number of nodes it contains.

2. A mirror method that accepts a binary tree and returns its mirror image; left and right are swapped.

3. A preorder method that accepts a binary tree and returns a linked list containing the elements of the tree listed in preorder.

   What is preorder? Let’s define it.

   A preorder traversal is a listing of the values in a binary tree. For a given tree, its preorder traversal is empty if the tree is empty. Otherwise, it starts with the value at the root of the tree, then contains the preorder traversal of the left subtree, then the preorder traversal of the right subtree.

4. A findPath method that accepts a binary tree and a value and if the tree contains the value (compare them using "equals"), returns a linked list of "left"s and "right"s representing the path from the root to the located value, ending with the string "here". So, for instance, if the way to get to the given node from the root is to go left, right, and left again, your list should contain four strings: "left", "right", "left", and "here".

Well! That sounds like quite enough for now.