Question

*****************************In Java***************************************In Java***********************************In Java*************************

In this problem, you will implement various algorithms operating on binary search trees. We have provided with you a standard implementation of a generic BST in BinarySearchTree.java. Note that this class is an abstract class, which means that some of its methods are not implemented. In previous assignments, you have implemented interfaces which specified methods that you needed to write. Very similarly, an abstract class is a class with some unimplemented methods (it can be thought of somewhat like an interface but with some methods actually implemented). You will need to write a BetterBST class which extends BinarySearchTree. Your BetterBST class can then be treated just like a regular BinarySearchTree, just with some additional functionality.

The methods that you will need to implement in BetterBST perform various algorithms on BST instances. For some of these methods, you may find it convenient to implement a private helper method as you did in previous assignments.

• public int height() - return the height of the BST
• public T imbalance() - check whether the tree is balanced. A balanced tree is one where every node’s left and right subtrees differ in height by no more than 1. Return the value at first node you find which has a height imbalance greater than 1 between its subtrees, or null if no such node exists (i.e. the tree is balanced). In class, we briefly discussed AVL trees, which enforce this balance condition.
• public BinarySearchTree<T> mirror() - return a mirrored version of the BST instance. That is, any node that is a left child becomes a right child and vice versa. You should not modify the BST instance itself. Instead, you should create a new BST instance and build it.
• public T smallestGreaterThan(T t) - given some generic comparable value t, find the smallest value in the BST that is larger than t. For example, if a binary search tree contains the values 1, 3, and 5, and the function is called with t = 2, it should return 3.
• public void prettyPrint() - “pretty print” the binary tree. For example, given a tree with root = 3, left child = 1, right child = 5, and where the root’s right child has left child = 4, the pretty print could look something like:

     3
 1       5
       4

There is no required format for the pretty print, however, it must clearly look like a tree!

Make sure you read the BST code in depth before you start implementing BetterBST. In particular, take note of the various internal methods, nested classes, and instance variables that you can access from BetterBST.

We will test this program with our own tester class in a separate file. You should also create a tester class for your own testing purposes. Your tester class will not be graded.

Answer 1

Hi, I have answered similar question before. Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. Thanks

// BetterBST.java

public class BetterBST<T extends Comparable<T>> extends BinarySearchTree<T> {

      @Override

      int height() {

            return height(root);

      }

      // recursive helper method to find the height of the tree, also helpful in

      // imbalance method

      private int height(BinaryNode<T> node) {

            // if node is null, returning 0 (end condition)

            if (node == null) {

                  return 0;

            }

            // finding height of left subtree

            int leftHeight = height(node.left);

            // finding height of right subtree

            int rightHeight = height(node.right);

            // finding which among the two is higher, and add 1 to it (current

            // level) and returning it

            return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);

      }

      @Override

      T imbalance() {

            // using helper method to find imbalance of tree

            return imbalance(root);

      }

      T imbalance(BinaryNode<T> node) {

            if (node == null) {

                  // end condition

                  return null;

            }

            // finding the height of left tree and right tree

            int heightLeft = height(node.left);

            int heightRight = height(node.right);

            // finding absolute difference

            int diff = Math.abs(heightLeft - heightRight);

            // if difference is greater than 1, returning current node's value

            if (diff > 1) {

                  return node.data;

            }

            // finding imbalance of left subtree

            T temp = imbalance(node.left);

            // returning temp if it is not null

            if (temp != null) {

                  return temp;

            }

            // finding imbalance of right subtree, and returning it

            temp = imbalance(node.right);

            return temp;

      }

      @Override

      BinarySearchTree<T> mirror() {

            // creating a BST

            BinarySearchTree<T> tree = new BetterBST<T>();

            // taking copy of this tree and assigning to the above tree

            tree.root = copy(root);

            // mirroring nodes of copied tree

            mirror(tree.root);

            // returning mirrored tree

            return tree;

      }

      // private helper method to copy a binary search tree, given a root node

      private BinaryNode<T> copy(BinaryNode<T> node) {

            if (node == null) {

                  // base condition.

                  return null;

            }

            // creating a node with data = node's data

            BinaryNode<T> root = new BinaryNode<T>(node.data);

            // copying left subtree and assigning to root.left

            root.left = copy(node.left);

            // copying right subtree and assigning to root.right

            root.right = copy(node.right);

            // returning copied tree

            return root;

      }

      // private helper method to mirror the nodes of a tree

      private void mirror(BinaryNode<T> node) {

            if (node == null) {

                  // end condition

                  return;

            }

            // swapping left and right nodes

            BinaryNode<T> temp = node.left;

            node.left = node.right;

            node.right = temp;

            // mirroring left subtree

            mirror(node.left);

            // mirroring right subtree

            mirror(node.right);

      }

      @Override

      T smallestGreaterThan(T t) {

            // using recursive method to find the smallest element which is greater

            // than t

            return smallestGreaterThan(t, root);

      }

      // recursive helper method to find the smallest element which is greater

      // than t

      private T smallestGreaterThan(T t, BinaryNode<T> node) {

            // if node is null, returning null.

            if (node == null) {

                  return null;

            }

            // if node is smaller than or equal to t, calling the method

            // recursively, passing the right subtree

            if (node.data.compareTo(t) <= 0) {

                  return smallestGreaterThan(t, node.right);

            }

            // if left node is null, we have found the smallest element greater than

            // t, returning it

            if (node.left == null)

                  return node.data;

            // otherwise, returning smallest element greater than t in left subtree

            return smallestGreaterThan(t, node.left);

      }

      @Override

      void prettyPrint() {

            prettyPrint(root, "");

      }

      // recursive method to print the BST. Even though specification is not given

      // I'm just writing this according to my understanding

      // here indentation specifies the indentation of the node

      void prettyPrint(BinaryNode<T> node, String indentation) {

            if (node == null) {

                  // end condition

                  return;

            }

            // printing right subtree if not null, one tab additional spacing before

            // it

            if (node.right != null) {

                  prettyPrint(node.right, indentation + "\t");

            }

            // printing current node, with indentation specified in parameter

            System.out.println(indentation + node.data);

            // printing left subtree if not null, one tab additional spacing before

            // it

            if (node.left != null) {

                  prettyPrint(node.left, indentation + "\t");

            }

      }

}

// Test.java

public class Test {

      public static void main(String[] args) {

            // creating a bst, adding some values, testing new methods

            BetterBST<Integer> bst = new BetterBST<Integer>();

            bst.insert(1);

            bst.insert(3);

            bst.insert(5);

            bst.insert(10);

            bst.insert(7);

            bst.insert(9);

            bst.insert(0);

            System.out.println("smallestGreaterThan(2): "

                        + bst.smallestGreaterThan(2));

            System.out.println("smallestGreaterThan(7): "

                        + bst.smallestGreaterThan(7));

            System.out.println("smallestGreaterThan(13): "

                        + bst.smallestGreaterThan(13));

            System.out.println("Height: " + bst.height());

            // imbalance() should return 1 (root value), because height of left

            // subtree of root is 1 and that of right subtree is 5, difference>1

            System.out.println("BST imbalance(): " + bst.imbalance());

            System.out.println("BST pretty printing:");

            bst.prettyPrint();

            BinarySearchTree<Integer> mirror = bst.mirror();

            System.out.println("Mirror: ");

            mirror.prettyPrint();

      }

}

//OUTPUT