package timedlab;

// This is identical to the BinaryTree from class // but you have some methods to fill out public class BinaryTree> { private Node root;

public BinaryTree() { this.root = null; //this.size = 0; } //////////// // Problems begin here! // Complete the method bodies where directed. // you don't have to write new methods or change the method signature ///////////

// Problem Tree 1 // 25 points // finish this method, printSortedTree // It will print out all the items stored in the tree // it will print them all out in sorted order.

// The recursive method that prints out the items in the tree // or subtree that starts at root. // Remember, the local variable root here is not necessarily THE root of the whole tree

public static > void printSortedTree(Node root) {

}

// Problem Tree 2 // 25 points // finish this method, which counts the number of Strings in the tree // which begin with the string prefix // Strings have a .startsWith(String) method to make this easy

// it's a recursive like above // you return an int here, so you don't need to print anything out public static int countStrings(Node root, String prefix) {

return -1; // replace this }

///////////////////// public int size() {

return this.size(this.root); }

private int size(Node root) { if(root == null) { return 0; }

//int mySize = 1; //int leftSize = size(root.left); //int rightSize = size(root.right); return 1 + size(root.left)+ size(root.right); }

public void add(E item) { this.root = add(this.root, item);

}

private Node add(Node root, E item) { if (root == null) { return new Node(item); } int comparisonResult = item.compareTo(root.item); if (comparisonResult == 0) { root.left = add(root.left, item); return root; } else if (comparisonResult < 0) { root.left = add(root.left, item); return root; } else { root.right = add(root.right, item); return root; }

}

public void remove(E item) { this.root = remove(this.root, item); }

private Node remove(Node root, E item) { if (root == null) { return null; } int comparisonResult = item.compareTo(root.item); if (comparisonResult < 0) { root.left = remove(root.left, item); return root; } else if (comparisonResult > 0) { root.right = remove(root.right, item); return root; } else { // root is the item we want to delete

// case 1, root is leaf if (root.left == null && root.right == null) { return null; } // case 2, root has only left child else if (root.left != null && root.right == null) { return root.left; } else if (root.left == null && root.right != null) { return root.right; } else { Node rootOfLeftSubtree = root.left; Node parentOfPredecessor = null; Node predecessor = null;

if (rootOfLeftSubtree.right == null) { root.item = rootOfLeftSubtree.item; root.left = rootOfLeftSubtree.left; return root; } else { parentOfPredecessor = rootOfLeftSubtree; Node current = rootOfLeftSubtree.right; while (current.right != null) { parentOfPredecessor = current; current = current.right; }

predecessor = current; root.item = predecessor.item; parentOfPredecessor.right = predecessor.left; return root;

} }

}

}

public boolean contains(E item) { return contains(this.root, item); }

private boolean contains(Node root, E item) { if (root == null) { return false; } int comparisonResult = item.compareTo(root.item); if (comparisonResult == 0) { return true; } else if (comparisonResult < 0) { return contains(root.left, item); } else { return contains(root.right, item); }

}

public String toString() { StringBuilder sb = new StringBuilder(); preOrderTraverse(root, 1, sb); return sb.toString(); }

private String toString(Node root) { if (root == null) { return ""; } String output = "";

output += root.item + " "; output += toString(root.left);

output += toString(root.right); return output;

}

private void preOrderTraverse(Node root, int depth, StringBuilder sb) { for (int i = 1; i < depth; i++) { sb.append(" "); // indentation } if (root == null) { sb.append("null "); } else { sb.append(root.toString()); sb.append(" "); preOrderTraverse(root.left, depth + 1, sb); preOrderTraverse(root.right, depth + 1, sb); } }

private static class Node> { private E item; private Node left; // left child private Node right; // right child

public Node(E item) { this.item = item; }

public String toString() { return item.toString(); } }

public static void main(String[] args) { BinaryTree tree = new BinaryTree();

printSortedTree(tree.root);

}

}