11. Binary Trees

Feel free to use your laptop
You are strongly encourage to work with others
- When you get stuck, ask those sitting around you for help
- Get used to working together in the labs
- Peer teaching and peer learning has been empirically shown to be very effective

Note

This lab focuses on manipulating binary node objects, not the development of an actual tree class. However, a tree structure is ultimately being created with the binary nodes.

11.1. Draw The Tree

Start with a scrap piece of paper
- The problems being solved are becoming more complex
- Visualizing what the code is doing by drawing it out may be very helpful

Draw the tree that the following code generates

public static void main(String[] args){
    BinaryNode<Integer> root = new BinaryNode<>(6);

    root.setLeft(new BinaryNode<>(2));
    root.setRight(new BinaryNode<>(8));

    root.getLeft().setLeft(new BinaryNode<>(1));
    root.getLeft().setRight(new BinaryNode<>(4));

    root.getRight().setLeft(new BinaryNode<>(7));
    root.getRight().setRight(new BinaryNode<>(9));

    root.getLeft().getRight().setLeft(new BinaryNode<>(3));
    root.getLeft().getRight().setRight(new BinaryNode<>(5));
}

11.2. Binary Node

Create a BinaryNode class
- This can be downloaded from here
Ensure the BinaryNode class is working by running the above main method for generating the tree

11.3. In-Order Traversal

Create a recursive inOrderTraversal
- Review the traversals if you do not remember what an inorder traversal is
public static <T> void inOrderTraversal(BinaryNode<T> current){ // Fill me in }

11.4. Number of Nodes

Write a recursive numberOfNodes method to count the number of nodes within the tree

public static <T> int numberOfNodes(BinaryNode<T> current){
    // Fill me in
}

11.5. Depth

Write a recursive treeDepth method to calculate the depth of the tree
- Be sure to remember the definition of the height of a tree
public static <T> int treeDepth(BinaryNode<T> current){ // Fill me in }

11.6. Balanced

Warning

This problem is more challenging than the previous. Feel free to jump to the Kattis problems if stuck.

Write a recursive isBalanced method to determine if a given tree is balanced
- Be sure to know the definition of a balanced tree
public static <T> boolean isBalanced(BinaryNode<T> current){ // Fill me in }