CSC1020 Homework 9

Overview

This is a series of Unit tests to verify the output of your methods. It is not comprehensive, but will test minimal functionality. Feel free to add your own tests to verify you code.

Requirements

  1. Preorder Traversal Write a method: public String preOrder() that returns the preorder traversal of a binary tree as a sequence of strings each separated by a space, omitting all null values.

  2. Postorder Traversal Write a method: public String postOrder() that returns the postorder traversal of a binary tree as a sequence of strings each separated by a space, omitting all null values.

  3. Inorder Traversal Write a method: public String inOrder() that returns the inorder traversal of a binary tree as a String. When constructing the String, place a left parenthesis before each subtree and a right parenthesis after each subtree. A space should exist both before and after an operator. For an empty subtree, display nothing. For example, the following expression tree: HW9 Tree would return: (((x) + (y)) * ((a) / (b)))

Note you will not be able to use the pre-existing inOrder() method to accomplish this.

  1. Height Write a method: public int height() that returns the height of the tree, where the height is defined as the depth of the deepest node in the tree (or the highest node level).

Using BiConsumer to Visit Nodes

A BiConsumer is a Functional Interface that makes visiting nodes fairly straightforward. Recall that a Functional Interface is an interface with exactly one method. These interfaces can be passed as parameters, effectively allowing us to pass methods into other methods. We do this to allow us the ability to have a single method that can do many different things. In the case of traversals this is especially important, because it is our only way to iterate through the tree, and we may have many different reasons to be iterating, but because it is recursive, we have to define what we are doing in the recursive call. Being able to write a single recursive method that can do anything we want to the tree is our goal.

A BiConsumer is an interface that takes two parameters (hence BiConsumer), performs some action using its single accept() method, and returns nothing (it “consumes” the data). In our BinaryTree, the BiConsumer will take as its parameters some data E and an Integer. The Integer will be used to keep track of the node level of the current node being visited. Not every application of the traversal will use the node level, and that is fine, but it may be needed for some traversals, so we add it to all of them.

When we pass the BiConsumer as a parameter, we may instantiate an instance of a BiConsumer (actually, an instance of an anonymous class that implements the BiConsumer) using a lambda expression or we may just pass the lambda expression itself:

BiConsumer<String, Integer> consumer =
(d, h) -> System.out.println(d);
tree.preOrder(consumer);

tree.preOrder((d, h) -> System.out.println(d));