Instructions

Copy the methods from your BinarySearchTree class from previous assignment

In this assignment, add the following methods. You are also given a method that will return a String that prints out the tree in a nice visual format.

// returns the lowest value according

// to the classes natural orderingpublic Comparable getLowest()

// returns the highest value according

// to the classes natural orderingpublic Comparable getHighest()

// returns true if the left and right side

// of the tree differ by 1 or less. public boolean isBalanced()

// returns a levelOrder representation of// the tree. You will need to use a queue

// datastructure for this.public String levelOrder()

Example output:

In order [10, 15, 20, 25, 35, 40, 45, 55, 60, 70, 80]

Pre order [60, 25, 15, 10, 20, 40, 35, 55, 45, 80, 70]

Post order [10, 20, 15, 35, 45, 55, 40, 25, 70, 80, 60]

Level Order [60, 25, 80, 15, 40, 70, 10, 20, 35, 55, 45]

Width 7

Levels 5

Lowest 10

Highest 80

isBalanced false

Binary Search Tree (Maximum of 5 levels shown.

60

|-----------------------^-----------------------|

25 80

|-----------^-----------| |.-----------^

15 40 70 |-----^-----| |-----^-----|

10 20 35 55

|--^

45

BinarySearchTree.java

public class BinarySearchTree {

private Node root;

public BinarySearchTree() { root = null; }

public void add(Comparable val) { root = add(val, root); }

private Node add(Comparable val, Node current) { if (current == null) { return new Node(val); }

if (val.compareTo(current.data) < 0) { current.left = add(val, current.left); } else if (val.compareTo(current.data) > 0) { current.right = add(val, current.right); } return current; } public boolean contains (Comparable val) { return contains(val, root); }

private boolean contains (Comparable val, Node current) { if (current == null) { return false; } else if (val.compareTo(current.data) < 0) { return contains(val, current.left); } else if (val.compareTo(current.data) > 0) { return contains(val, current.right); } else { return true; } }

// The following three methods should include commas and square brackets // For example, [1, 3, 5, 7, 9] public String inOrder() { String str = inOrder(root); return "[" + str.substring(0, str.length() - 2) + "]"; }

private String inOrder(Node current) { if (current == null) { return ""; } return inOrder(current.left) + current.data + ", "+ inOrder(current.right); }

public String preOrder(){ String str = preOrder(root); return "[" + str.substring(0, str.length() - 2) + "]"; } private String preOrder(Node current) { if (current == null) { return ""; } return current.data + ", "+ preOrder(current.left) + preOrder(current.right); } public String postOrder(){ String str = postOrder(root); return "[" + str.substring(0, str.length() - 2) + "]"; } private String postOrder(Node current) { if (current == null) { return ""; } return postOrder(current.left) + postOrder(current.right) + current.data + ", "; }

public int getHeight() { return getNumLevels()-1; }

public int getWidth(){ return getWidthLeft(root) + getWidthRight(root) -1; }

private int getWidthLeft(Node current){ if(current == null){ return 0; } else { if(current.left != null){ return 1 + getWidthLeft(current.left); } else { return 1 + getWidthLeft(current.right); } } }

private int getWidthRight(Node current){ if(current == null){ return 0; } else { if(current.right != null){ return 1 + getWidthRight(current.right); } else { return 1 + getWidthRight(current.left); } } }

public int getNumLeaves(){ return (getNumLeaves(root))/2; }

private int getNumLeaves(Node current){ if(current == null){ return 1; } else{ return getNumLeaves(current.right) + getNumLeaves(current.left); } }

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

private int getNumLevels(Node current){ if (current == null) { return 0; } else { int numLeft = getNumLevels(current.left); int numRight = getNumLevels(current.right); if (numLeft > numRight) { return 1 + numLeft; } else { return 1 + numRight; } } }

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

private int size(Node current){ if(current == null){ return 0; } else{ return 1+size(current.right)+size(current.left); } }

public String toString(){ return inOrder(); }

}

Main.java

class Main { public static void main(String[] args) { BinarySearchTree tree = new BinarySearchTree();

tree.add(60); tree.add(25); tree.add(15); tree.add(40); tree.add(80); tree.add(10); tree.add(70); tree.add(40); tree.add(55); tree.add(20); tree.add(35); tree.add(45);

System.out.println(); System.out.println("In order " + tree.inOrder()); System.out.println("Pre order " + tree.preOrder()); System.out.println("Post order " + tree.postOrder()); System.out.println("Level Order " + tree.levelOrder()); System.out.println("Width " + tree.getWidth()); System.out.println("Levels " + tree.getNumLevels()); System.out.println("Lowest " + tree.getLowest()); System.out.println("Highest " + tree.getHighest()); System.out.println("isBalanced " + tree.isBalanced());

System.out.println(tree.printTree(5));

} }

Node.java

class Main { public static void main(String[] args) { BinarySearchTree tree = new BinarySearchTree();

tree.add(60); tree.add(25); tree.add(15); tree.add(40); tree.add(80); tree.add(10); tree.add(70); tree.add(40); tree.add(55); tree.add(20); tree.add(35); tree.add(45);

System.out.println(); System.out.println("In order " + tree.inOrder()); System.out.println("Pre order " + tree.preOrder()); System.out.println("Post order " + tree.postOrder()); System.out.println("Level Order " + tree.levelOrder()); System.out.println("Width " + tree.getWidth()); System.out.println("Levels " + tree.getNumLevels()); System.out.println("Lowest " + tree.getLowest()); System.out.println("Highest " + tree.getHighest()); System.out.println("isBalanced " + tree.isBalanced());

System.out.println(tree.printTree(5));

} }