Implement a method to convert a tree to a string.

Your HW8Tree class must include the BinaryNode.java code.

Your HW8Tree class must have an instance variable that refers to (points to) the root of a tree. This class must provide these recursive methods:

a public boolean add(E item, boolean[] left) method to add values to the tree. Starting from the root, at each node, the method must go down to the left if the corresponding position in the array is true, and otherwise must go down to the right. Once a null pointer is reached, the item must be added to the tree in place of the null pointer.

It is an error if the array of booleans is too short. In this case, the add method should throw a RuntimeException.

a public List toList() method that stores in a list a reference to each of the objects in the tree, as visited in an in-order traversal. You can choose what kind of list to use, as long as it satisfies the List interface.

a public String toString() method that converts the tree to a string, in the same way that folders are printed: the root is first, followed by the children of the node indented 4 spaces, the grandchildren indented 8 spaces, and so on.

Each of these methods must use recursion to traverse the tree. In each case, the recursion may be in a helper method.

For example, consider a tree with root "hello". "hello" has two children, "foo" and "bar". "foo" has children "world", and "baz", and "bar" has children "bug" and "loop".

The toString method converts the tree to the following string:

hello foo world baz bar bug loop 

The above example shows what the string looks like when it is printed. As a string, it actually looks like this:

"hello foo world baz bar bug loop " 

As many of you already know, " " is the newline character in Java.

Calling toList should return a list with contents world, foo, baz, hello, bug, bar, loop. Only this order correctly reflects an in-order traversal.

To add the string "fum" below and to the right of "bug", we would call

 boolean[] lefts = { false, true, false}; HW8Tree myTree = new HW8Tree (); // fill in the tree until it matches the example above, then myTree.add ("fum", lefts); 

__________________________________________________________________________________________________

==============================BinaryNode.java=================================

private static class BinaryNode { private T item; private BinaryNode left; private BinaryNode right; /** * constructor to build a node with no subtrees * @param the value to be stored by this node */  private BinaryNode(T value) { item = value; left = null; right = null; } /** * constructor to build a node with a specified (perhaps null) subtrees * @param the value to be stored by this node * @param the left subtree for this node * @param the right subtree for this node */ private BinaryNode(T value, BinaryNode l, BinaryNode r) { item = value; left = l; right = r; } } 

Not sure if this will help, but what I have previously:

import lab.solution.BinaryTree;

===============================Main.java===============================

public class Main {

/** * Write the function in the BinaryTree class to determine whether or not a given binary tree is a max or min heap */ public static void main(String args[]) { //True BinaryTree bt = new BinaryTree(); bt.add(50); bt.add(20); bt.add(25); bt.add(13); bt.add(12); bt.add(15); bt.add(2); System.out.println(bt.isMaxHeap());

//False BinaryTree bt1 = new BinaryTree(); bt1.add(50); bt1.add(20); bt1.add(25); bt1.add(26); bt1.add(12); bt1.add(15); bt1.add(2); System.out.println(bt1.isMaxHeap());

//False BinaryTree bt2 = new BinaryTree(); bt2.add(50); bt2.add(20); bt2.add(25); bt2.add(13); bt2.add(12); bt2.add(15); bt2.add(51); System.out.println(bt2.isMaxHeap());

//False BinaryTree bt3 = new BinaryTree(); bt3.add(50); bt3.add(20); bt3.add(25); bt3.add(31); bt3.add(12); bt3.add(15); bt3.add(2); System.out.println(bt3.isMaxHeap());

//What do you think this should return?? :) //What if we made equal cases not allowed? (IE. A parent node 30 with child node 30 is wrong for a max heap) BinaryTree bt4 = new BinaryTree(); bt4.add(50); bt4.add(20); bt4.add(25); //This parent bt4.add(13); bt4.add(12); bt4.add(15); bt4.add(25); //Has this child System.out.println(bt4.isMaxHeap()); //Try writing a set of test cases for minHeap tests BinaryTree bt5 = new BinaryTree(); bt5.add(2); bt5.add(11); bt5.add(13); bt5.add(15); bt5.add(25); bt5.add(31); bt5.add(50); System.out.println(bt5.isMinHeap()); }

}

==================================BinaryTree.java===============================

import java.util.LinkedList; import java.util.Queue;

public class BinaryTree { private Node root; public BinaryTree() { this.root = null; } public BinaryTree(Node root) { this.root = root; }

/** * Implement this function. * @return true if if our tree is a Max Heap, false otherwise. */ public boolean isMaxHeap() { Node temp = root; if (temp.getLeft().getItem() < root.getItem() && temp.getRight().getItem() < root.getItem()) { temp = temp.getLeft(); return true; } while(temp != null) { if (temp.getItem() > temp.getLeft().getItem()) { //temp = temp.getLeft(); } } return false; } /** * Implement this function. * @return true if if our tree is a Min Heap, false otherwise. */ public boolean isMinHeap() { Node temp = root; if (temp.getLeft().getItem() > temp.getItem() && temp.getRight().getItem() > temp.getItem()) { return true; } return false; } /** * @return true if our tree is a Binary Tree, false if it's not a Binary Tree * If root is null, return false */ public boolean isBST() { Node temp = root; if(temp == null) { //A null tree/empty tree is still a BST return true; } else { Queue> q = new LinkedList>(); q.offer(root); while(!q.isEmpty()) { if(q.peek().getLeft() != null) { q.offer(q.peek().getLeft()); } if(q.peek().getRight() != null) { q.offer(q.peek().getRight()); } //The one instance where I cannot find an item that definitely exists in my tree //using a BST "find" logic, then I know my tree is not a BST if(!canFindItem(q.poll().getItem())) return false; } } return true; } public boolean canFindItem(int item) { if(root != null) { Node temp = root; while(temp != null) { if(temp.getItem() == item) { return true; } if(temp.getItem() > item) { temp = temp.getLeft(); } else { temp = temp.getRight(); } } } return false; } public void add(int item) { Node temp = root; Queue> q = new LinkedList>(); if(temp == null) { root = new Node(item); } else { q.offer(temp); while(!q.isEmpty()) { //If there is no children, add left if(q.peek().getLeft() == null && q.peek().getRight() == null) { temp = q.poll(); temp.setLeft(new Node(item)); break; } //Left exists but right does not exist, add to the right else if(q.peek().getLeft() != null && q.peek().getRight() == null) { temp = q.poll(); temp.setRight(new Node(item)); break; } //Both not null, need to traverse both directions else { q.offer(q.peek().getLeft()); q.offer(q.peek().getRight()); q.poll(); } } } } /** * Gets the level that the item is on in the BST * @param item -- Item to find the level of * @return level the item is on in the BST, returns -1 */ public int getLevel(int item) { int level = 0; Node temp = root; while(temp != null && temp.getItem() != item) { if(temp.getItem() < item) { temp = temp.getRight(); } else { temp = temp.getLeft(); } level++; } return (temp == null) ? -1 : level; } public void printAsString() { if(root != null) { Queue> q = new LinkedList>(); q.offer(root); while(!q.isEmpty()) { if(q.peek().getLeft() != null) { q.offer(q.peek().getLeft()); } if(q.peek().getRight() != null) { q.offer(q.peek().getRight()); } System.out.println(q.poll().getItem()); } } }

}

==============================Node.java==============================

public class Node {

private Node left, right; private E item; public Node(E item) { this.item = item; } public void setItem(E item) { this.item = item; } public E getItem() { return this.item; } public void setLeft(Node left) { this.left = left; } public Node getLeft() { return this.left; } public void setRight(Node right) { this.right = right; } public Node getRight() { return this.right; } }

________________________________________________________________________________________________

RuntimeException: (http://docs.oracle.com/javase/8/docs/api/java/lang/RuntimeException.html)

List interface: (http://docs.oracle.com/javase/8/docs/api/java/util/List.html)

Please briefly comment what parts of the code does, Thanks.