binary search tree in java //explaination plz solve all the Qs (methods) and rea

ID: 3834620 • Letter: B

Question

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()));

}

Explanation / Answer