public class BinaryTree { private T data; private BinaryTree parent; private BinaryTree left; private BinaryTree right; public BinaryTree() { parent = left = right = null; data = null; } public void makeRoot(T data) { if (!isEmpty()) { System.out.println("Can't make root. Already exists"); } else this.data = data; } public void setData(T data) { this.data = data; } public void setLeft(BinaryTree tree) { left = tree; } public void setRight(BinaryTree tree) { right = tree; } public void setParent(BinaryTree tree) { parent = tree; } public T getData() { return data; } public BinaryTree getParent() { return parent; } public BinaryTree getLeft() { return left; } public BinaryTree getRight() { return right; } public void attachLeft(BinaryTree tree) { if (tree==null) return; else if (left!=null || tree.getParent()!=null) { System.out.println("Can't attach"); return; } else { tree.setParent(this); this.setLeft(tree); } } public void attachRight(BinaryTree tree) { if (tree==null) return; else if (right!=null || tree.getParent()!=null) { System.out.println("Can't attach"); return; } else { tree.setParent(this); this.setRight(tree); } } public BinaryTree detachLeft() { if (this.isEmpty()) return null; BinaryTree retLeft = left; left = null; if (retLeft!=null) retLeft.setParent(null); return retLeft; } public BinaryTree detachRight() { if (this.isEmpty()) return null; BinaryTree retRight = right; right =null; if (retRight!=null) retRight.setParent(null); return retRight; } public boolean isEmpty() { if (data == null) return true; else return false; } public void clear() { left = right = parent =null; data = null; } public BinaryTree root() { if (parent == null) return this; else { BinaryTree next = parent; while (next.getParent()!=null) next = next.getParent(); return next; } } public static  void preorder(BinaryTree t) { if (t!=null) { System.out.print(t.getData()+"\t"); preorder(t.getLeft()); preorder(t.getRight()); } } public static  void inorder(BinaryTree t) { if (t!=null) { inorder(t.getLeft()); System.out.print(t.getData() + "\t"); inorder(t.getRight()); } } public static  void postorder(BinaryTree t) { if (t!=null) { postorder(t.getLeft()); postorder(t.getRight()); System.out.print(t.getData() + "\t"); } } 

//This is just a starter demo program //TODO: Get inputs from the user. Do not hardcode them. public class BinaryTreeDemo { public static void main(String[] args) { BinaryTree A = new BinaryTree(); BinaryTree B = new BinaryTree(); BinaryTree C = new BinaryTree(); BinaryTree D = new BinaryTree(); BinaryTree E = new BinaryTree(); BinaryTree F = new BinaryTree(); A.makeRoot("A"); B.makeRoot("B"); C.makeRoot("C"); D.makeRoot("D"); E.makeRoot("E"); F.makeRoot("F"); A.attachLeft(B); A.attachRight(C); B.attachLeft(D); B.attachRight(E); D.attachLeft(F); System.out.print("Preorder:\t"); BinaryTree.preorder(A); System.out.println(); System.out.print("Inorder:\t"); BinaryTree.inorder(A); System.out.println(); System.out.print("Postorder:\t"); BinaryTree.postorder(A); System.out.println(); } } 

Download the following files from the course website (alongside the Lab6 link): BinaryTree.java, Binary TreeDemo.java We discussed these in the lectures. Study and understand the methods. Step 1: Add a recursive method to BinaryTree java to find the number of nodes in a binary tree It is easy to design this recursive method. The solution is given below if the binary tree is empty, then the number of nodes is zero, otherwise, it is equal to one plus number of nodes in the left subtree plus number of nodes in the right subtree Test the method by making appropriate changes to BinaryTreeDemo java for at least three different inputs Now design the following: Step 2: Add a recursive method to BinaryTree java to find the height of a binary tree. Test the method for at least three different inputs. Step 3: A binary tree is height balanced if, for every node in the tree, the height of its left subtree differs from the height of its right subtree by no more than one. In other words, either