I'm having trouble understanding Binary trees. This is my study guide prompt for my final tommorow

The optimization of binary trees is an interesting study in recursion The diameter of a binary tree is a longest path or route between any two nodes in that tree. The path may or may not go through the root. Consider the following diagrams: In both trees, the diameter is 6. (Notice that in the above trees, the numbers in each node cannot be the actual data values in the node, because the trees are not sorted by those values.) The height of a node is the number of edges from the node to the deepest leaf. The height of a tree is the height of the root of that tree. The diameter of any tree can be found by calculating the maximum of The diameter of the left subtree The diameter of the right subtree The longest path between two nodes which pass through the root Notice that the first two numbers can be solved recursively. The longest path between two nodes which pass through the root can be found by calculating: 1 + height of left subtree + height of right subtree. First, duplicate the classes in the BinaryTreeDemo from the lecture. You can download them from Blackboard. Next, create a helper method in the StudentTree class called getHeight, which will look something like the following: private int getHeight(StudentNode subTreeRoot) { if (subTreeRoot == null) { return 0 ; } return 1 + Math.max(getHeight(subTreeRoot.leftLink), getHeight(subTreeRoot.rightLink)) ; }

Notice the simple recursive nature of this method. (What is its base case?). Well also require a helper method in the StudentTree class called getDiameter, which will look something like the following: private int getDiameter(StudentNode subTreeRoot) {

// If we are at a leaf, then done

if (subTreeRoot == null) { return 0 ; }

// Calculate the height of the left and right subtrees int leftHeight = getHeight(subTreeRoot.leftLink); int rightHeight = getHeight(subTreeRoot.rightLink); // Calculate the diameter of the left and right subtrees int leftDiameter = getDiameter(subTreeRoot.leftLink); int rightDiameter = getDiameter(subTreeRoot.rightLink);

// Find the maximum of the leftsubtree diameter, the // rightsubtree subdiameter, and the longest path which // goes through the root return Math.max(leftHeight + rightHeight + 1, Math.max(leftDiameter, rightDiameter)); }

Again a simple recursive method. Finally make overloaded, non-recursive versions of the helper methods which are available to the outside world. They will return the height and diameter of the entire tree:

public int getHeight() { return getHeight(root) ; }

public int getDiameter() { return getDiameter(root) ;

} Now build several trees and determine their heights and diameters.

Tree 1: A tree of students entered in alphabetic (lexicographic) order:

Enter these names into a binary tree in this order: Albert, Barbara, Charlie, Dexter, Eduardo, Frank, George, and Henrietta.

Tree 2: A tree of students entered in reverse alphabetic order (use the names above entered in reverse order)

Tree 3: The tree of students above entered so that three tree looks like the following:

Charlie

Barbara Eduardo

Albert Dexter George

Frank Henrietta

Notice the order of the tree when traversed in the InOrder. What about PreOrder? Trees 4 and 5: Develop two trees of your own, one which duplicates the structure on the left and one duplicating the structure on the right:

When you are done, submit the following: Listings of all classes A Printscreen of the heights and diameters for the five trees above (three where the detail was given, and the two trees of your own design