binary search tree in java //explaination

plz solve all the Qs (methods) and read the Qs carefully. I included the class BST node , class BST(to write all the methods )and test (main methode)

HERE R THE Qs

1. A method to count the number of nodes with 2 children (child may be a single node or a sub-tree)

2. A method to print a BST sorted in reverse order

3. A method to print a BST in breadth first order

4. A method reconstruct a BST given its preorder traversal

5. A method to check if two BSTs are identical

6. A method mirror() to create a mirror image of BST

7. A method to check if a BST T1 is a mirror of T2

8. A method to find the common elements between two BSTs, and insert them in 3rd BST

class BST node

package bst;

public class BSTclassNode {

private Comparable value; private BSTclassNode left; private BSTclassNode right;

public BSTclassNode(Comparable value) { this.value = value; left = null; right = null; }

public boolean add(Comparable value) { if (value.compareTo(this.value) == 0) { return false; } else if (value.compareTo(this.value) < 0) { if (left == null) { left = new BSTclassNode(value); return true; } else { return left.add(value); } } else if (value.compareTo(this.value) > 0) { if (right == null) { right = new BSTclassNode(value); return true; } else { return right.add(value); } } return false; }

public boolean search(Comparable value) { if (value.compareTo(this.value) == 0) { return true; } else if (value.compareTo(this.value) < 0) { if (left == null) { return false; } else { return left.search(value); } } else if (value.compareTo(this.value) > 0) { if (right == null) { return false; } else { return right.search(value); } } return false; }

public void printInOrder(BSTclassNode node) { if (node == null) { return; }

printInOrder(node.left); System.out.print(node.value+" ---> " ); printInOrder(node.right); }

public void postOrder(BSTclassNode node) { if (node == null) { return; }

postOrder(node.left); postOrder(node.right); System.out.println( node.value+" ---> "); }

public void preOrder(BSTclassNode node) { if (node == null) { return; } System.out.println( node.value+" --->"); preOrder(node.left); preOrder(node.right); }

public int countNodes(BSTclassNode node) { int count = 0; if (node == null) { return 0; } count += countNodes(node.left); count++; count += countNodes(node.right); return count; }

public Comparable getMax() { if (right == null) { return value; } else { return right.getMax(); } }

public Comparable getMin() { if (left == null) { return value; } else { return left.getMin(); } }

public int countAncestors(Comparable v, int currentAncestor) { if (value.compareTo(v) == 0) { return currentAncestor; } else { if (v.compareTo(value) < 0 && left != null) { return left.countAncestors(v, currentAncestor + 1); } else if (v.compareTo(value) > 0 && right != null) { return right.countAncestors(v, currentAncestor + 1); } else { return 0; } } }

public int countLeaves() { if (left == null && right == null) { return 1; } else { int count = 0; if (left != null) { count += left.countLeaves(); } if (right != null) { count += right.countLeaves(); } return count; } }

public int countEven() { int count = 0; if (value instanceof Integer && ((Integer) value) % 2 == 0) { count++; } if (left != null) { count += left.countEven(); } if (right != null) { count += right.countEven(); } return count; }

public int countComparisons(Comparable v) { int cmp = v.compareTo(value); if (cmp == 0) { return 1; } else { if (cmp < 0 && left != null) { return 1 + left.countComparisons(v); } else if (cmp > 0 && right != null) { return 1 + right.countComparisons(v); } else { return 1; }

}

} }

BST class

package bst;

public class BinarySearchTree {

private BSTclassNode root;

public BinarySearchTree() { root = null; }

public boolean add(Comparable value) { if (root == null) { root = new BSTclassNode(value); return true; } else { return root.add(value); } }

public boolean search(Comparable value) { if (root == null) { return false; } else { return root.search(value); } }

public void printInOrder() { if (root == null) { return; } else { root.printInOrder(root); } }

public void postOrder() { if (root == null) { return; } else { root.printInOrder(root); } }

public void preOrder() { if (root == null) { return; } else { root.printInOrder(root); } }

public int countNodes() { if (root == null) { return 0; } else { return root.countNodes(root); } }

public Comparable getMax() { if (root == null) { return 0; } else { return root.getMax(); } }

public Comparable getMin() { if (root == null) { return 0; } else { return root.getMin(); } }

public int countAncestors(Comparable v) { if (root == null) { return 0; } else { return root.countAncestors(v, 0); } }

public int countLeaves() { if (root == null) { return 0; } else { return root.countLeaves(); } }

public int countEven() { if (root == null) { return 0; } else { return root.countEven(); } }

public int countComparisons(Comparable v) { if (root == null) { return 0; } else { return root.countComparisons(v); } }

}

Test BST

package bst;

import java.io.File; import java.io.FileNotFoundException; import java.util.Random; import java.util.Scanner;

public class TestBST {

public static void readFile(String filename, BinarySearchTree bst) { try { Scanner in = new Scanner(new File(filename)); int count, m, n, diff, elem; count = in.nextInt(); m = in.nextInt(); n = in.nextInt(); diff = n - m; Random random = new Random(); System.out.println("Adding " + count + " elements in the range of " + m + " - " + n);

int i = 0;

while (i < count) { elem = m + random.nextInt(diff); if (bst.search(elem) == true) { continue; } System.out.println("Adding " + elem); bst.add(elem); i++; } System.out.println("The BST in inorder after adding numbers as specified in file is "); bst.printInOrder(); } catch (FileNotFoundException e) { System.out.println("File not found " + filename); System.out.println("No nodes were added to BST"); } }

public static void main(String[] args) { BinarySearchTree myBST = new BinarySearchTree();

String filename = "bstvalues.txt"; readFile(filename, myBST);

System.out.println(" printed post order "); myBST.postOrder(); System.out.println(" printed pre order"); myBST.preOrder(); System.out.println(" printed in order"); myBST.printInOrder(); System.out.println("The number of nodes is " + myBST.countNodes()); System.out.println("Searching for 13 " + myBST.search(13)); System.out.println("Searching for 8 " + myBST.search(8)); System.out.println("getting max number in BST " + myBST.getMax()); System.out.println("getting min number in BST " + myBST.getMin()); System.out.println("The number of leaves is " + myBST.countLeaves()); System.out.println("getting max number in BST " + myBST.getMax()); System.out.println("The number of ancestors for " + myBST.getMax() + " is " + myBST.countAncestors(myBST.getMax())); System.out.println("The number of even nodes in the tree are : " + myBST.countEven()); System.out.println("The number of comparsions for " + myBST.getMax() + " is " + myBST.countComparisons(myBST.getMax()));

}

}