Details Given the BST class template (see BST.java) you are toimplement some new operations (that is, instance methods of the BSTclass) for the BST class.

1. heightBalance – this will “rebalance” the BST so thatit is height balanced. This will be described below in detail. Thismethod will not have any parameters.

2. isHeightBalanced – this will return a boolean statingwhether the BST is height balanced or not. This method will returntrue if the tree is height-balanced, and false if it is not. Adefinition of height balanced is given in the discussion of theRebalance operation.

3. join – this will join two BSTs into a single BST.This will be described in below in detail.

6

4 11

2 5 7 12

1 3 9

8 10

Figure 1: This tree is not height-balanced

6

4 11

2 5 7 12

1 3

Figure 2: This tree is height-balanced

Height balancing

Suppose that height(v) returns the height of BST rooted at nodev. Recall the that height of a (sub)tree rooted at a node v is themaximum number of edges from v to any leaf node. Recall also thatthe height of an empty tree is -1 and height of a tree with onenode is 0. Consider the following tree.

A BST is height-balanced if for each node u in the BST,|height(u.left) – height(u.right) | ≤ 1, where u.left is the leftsubtree of u and u.right is the right subtree of u. The rebalancemethod will take the current BST and rebalance it so it isheight-balanced.

Consider the BST given in Figure 1. This tree is notheight-balanced. If you look at the node 7, its left subtree (whichis empty) has height -1, while it right subtree has height 2.Another node that shows that this tree is not height-balanced isnode 11. On the other hand, the BST given in Figure 2 isheight-balanced.

The algorithm to rebalance a BST so that it is height-balancedcan be done using the two steps as follows:

Step 1: You need to “listify” the BST. That is, turn the currentBST into one in which each non-leaf node has only a right child(and no left child). This BST will look like a long linked-list. Toachieve this, do the following:

1. Recursively listify the left child of the root (if there is aleft child),

2. Recursively listify the right child of the root (if there isa right child),

3. Link the root onto the bottom end of the listified left childand then link the listified right child as the right child of theold root.

Note that the new root of this tree will be the root of thelistified left child. Note that the term “root” in the abovedescription of the algorithm refers to the root of the subtreein

question. The base case could be that a tree consisting of onenode which is alreadyy listified. The recursive part should returna reference to the root of the listified tree that itconstructs.

In your BST class, you should implement a public driver methodlistify along with a recursive private helper method with the samename that does the actual work of listifying a BST.

If you listified the BST given in Figure 1, the resultinglistified BST is given by Figure 3

1

2

3

4

5

6

7

8

9

10

11

12

Figure 3: Listified BST of the BST given in Figure 1

Step 2: You need to height balance the listified BST. That is,you need to take the listified BST from step 1 and manipulate it sothat the resulting BST is height-balanced. To achieve this, do thefollowing:

1. Find the middle value of the tree – the value that is in themiddle of the sorted order of the values stored in the tree. Thenode containing the middle value will be the root of the resultingheight-balanced tree.

2. Split the listified tree into three disjoint pieces:

(a) The list of nodes containing values less than the middlevalue.

(b) The node containing the middle value – This node will be theroot of the resulting height-balanced tree.

(c) The list of nodes containing values greater than the middlevalue.

6

3 9

1 4 7 11

   2 5 8 10 12

  

Figure 4: Height-balanced BST of the listified BST given inFigure 3

3. Recursively height balance the nodes whose values are lessthan the middle value, and make it the left child of the nodecontaining the middle value.

4. Recursively height-balance the nodes whose values are greaterthan the middle value, and make it the right child of the nodecontaining the middle value.

For the base case, you could used the fact that a single node isalready height-balanced, and a two-node tree is alsoheight-balanced. Make sure that left and/or right references areset to null where appropriate. The recursive part should return areference to the root of the height-balanced tree that itconstructs.

In your BST class, you should implement a public driver methodheightBalance along with a recursive private helper method with thesame name that does the actual work of height-balancing thelistified BST from step 1.

Figure 4 is the result of height-balancing the listified BSTgiven in Figure 3. Depending on how you define the middle value(using floor or ceiling when dividing the number of nodes by 2),you could get a slightly different (yet still height-balanced)BST.

Important: In these two steps, you arenot allowed to create or destroy nodes. If you break thisrule, you will be heavily penalized. The nodes in the tree shouldmerely be moved around and relinked. Do not change the data valuestored (that is, the value stored in variable key) in a node.Furthermore, to do this operation, it is helpful to know the numberof nodes in a given subtree of the BST you are working with. Youcould either do a traversal of the tree to count the number ofnodes before beginning it, or you could store the number of nodesin the tree as part of the tree class (any insertion or deletionroutines would, of course, have to correctly update the number ofnodes).

Join

The join operation is to take two BSTs, join them into oneheight-balance BST. To implement the join operation you will makeuse of the operations above. Since this is an instance method ofthe BST class, one of the input trees, which we’ll denote by T1, isimplicit. The other tree, which we’ll call T2, will be passed in asan argument to your join method. There are two scenario/cases toconsider.

Easy Case: Suppose the maximum value in one tree is less thanthe minimum value in the other tree. If the maximum value in T1 ≤the minimum value in T2. Then make the root of T2 the right childof the node in T1 containing the largest element. Otherwise, if themaximum value in T2 ≤ the minimum value in T1. Then make the(current) root of T1 the right child of the node in T2 containingthe largest element, and set the root of T1 to be the root of T2.The node containing the minimum and maximum values can be obtainedusing the methods that you have already implemented above. Then youshould call heightBalance to height-balance your the BST T1. Figure5 shows an example of a join (before height balancing). Then toheight-balance the BST T1.You should make T2 the empty tree (bysetting its root variable to null) before returning. Note that inthis case, you should not create or destroy any nodes. Your joinedtree should be constructing simply by relinking the existingnodes.

2

1 3

4

T1

9

8 10

T2

2

1 3

4

9

8 10

T1.join(T2)

Figure 5: Joining two BSTs-easy case

7

1 12

       15

T1

9

8 10

T2

    7

1   12

      15

   8

      9

         10

T1.join(T2)

Figure 6: Joining two BSTs : harder case

Harder Case: In this case, there is no nice separation of thevalues in the two trees. Some of the values of one tree fallbetween the smallest and largest values in the other tree. In thiscase, repeatedly remove a node of minimum value from T2 (using thedeleteMin operation you have implemented already) and insert itinto the implicit BST (T1). Then you should call heightBalance toheight-balance your the BST T1. Figure 6 illustrates the result ofjoining two trees (but before height balancing). In this example,you would remove node 8 from T2, insert it to T1, remove node 9,insert it to T1 and finally remove node 10, insert it to T1. Inthis case, you are allowed to create new nodes when doing aninsertion (if you are using the existing insert method to insertinto the BST).

Your Main Class

You should create a file called A3.java that will contain themain method along with a modified BST class that will contain yourimplemention of the methods required. You can copy contents ofBST.java into this java file (but make sure the class is NOTdeclared public). In your main method you will prompt the user fora filename that contains the input data, which consists of two (2)trees.

Each tree in the file will begin with the number of values inthe tree, followed by that number of values, which should beinserted one by one into an empty tree. For example,

4

7

1

12

15

represents the tree T1 in Figure 6.

A complete input file may look like:

4

7

1

12

15

3

9

8

10

representing the trees T1, T2 respectively in Figure 6. You mayalways assume that the input is correct and that both trees in theinput file are non-empty.

After you have read in the two trees and created two BST objects(say T1, T2) from the input, you should:

1. print the first tree (T1) using an inorder traversal.

2. print the height of the tree.

3. print whether the tree is height-balanced or not.

4. print the second tree (T2) using an inorder traversal.

5. print the height of the tree.

6. print whether the tree is height-balanced or not.

7. perform the join operation T1.join(T2).

8. print the tree T1 using an inorder traversal.

9. print the height of the tree.

10. print whether the tree is height-balanced or not. sampleoutput (for the sample data file above):

Input filename is: a4test1.txt

1 7 12 15

height is: 2

Tree is height-balanced.

8 9 10

height is: 1

Tree is height-balanced.

1 7 8 9 10 12 15

height is: 2

Tree is height-balanced.

End of Processing.

BST.Java

//sample implementation of a BST

class BST {

  

   Node root; //reference to root of the binary searchtree

  

   public BST() {

       root = null;

   }

  

   //iterative insert

   public void insert(int val) {

       Node newNode,prev,curr;

       boolean done = false;

       prev = null;

       curr = root;

      

       newNode = newNode(val,null,null);

      

       if (root == null) {

           root =newNode;

       }

       else {

           while (curr!= null) {

              prev = curr;

              if (val < curr.key)

                  curr = curr.left;

              else

                  curr = curr.right;

           }

           if (val <prev.key)

              prev.left = newNode;

           else

              prev.right = newNode;

       }  

   }

   //recursive insert public drive method

   public void insertR(int val) {

       Node newNode;

      

       if (root == null) {

           root = newNode(val,null,null);

       }

       else {

          insertR(null,root,val);

       }

   }

  

   //recursive insert private helper method.

   //this method does the actual insertion into anon-empty tree

   private void insertR(Node prev, Node curr, int val){

   //prev-reference to previous node beingconsidered.

   //curr-reference to current node beingconsidered.

   //val – value to insert.

       Node newNode;

      

       if (curr == null) {   //base case

           newNode = newNode(val,null,null);

           if (val <prev.key )

              prev.left = newNode;

           else

              prev.right = newNode;

       } //recursive case

       else {

           if (val <curr.key)

              insertR(curr,curr.left,val);

           else

              insertR(curr,curr.right,val);

       }

   }  

  

   //iterative search

   public boolean search(int key) {

       Node curr=root;

       boolean result = false;

      

       while (curr !=null) {

           if (curr.key== key) {

              result = true;

              break;

           }

           else if (key< curr.key)

              curr = curr.left;

           else

              curr = curr.right;     

       }

       return result;

   }

  

   //recursive search

   public boolean searchR(int key) { //drivermethod

       return searchR(key,root);

   }

  

   //this method does the actual recursivesearching.

   private boolean searchR(int key, Node curr) {

       boolean result = false;

       if (curr !=null) {

           if (curr.key== key)

              result = true;

           else if (key< curr.key)

              result = searchR(key,curr.left);

           else

              result = searchR(key,curr.right);

       }

       return result;

   }

  

   //inorder traversal (recursive)

   private void inorder(Node curr) {

       if (curr != null) {

          inorder(curr.left);

          curr.print();

          inorder(curr.right);

          

       }

   }

  

   public void inorder() {

       inorder(root);

   }

   class Node {

       int key;

       Node left;

       Node right;

      

       public Node(int val, Node l,Node r) {

           key =val;

           left = l;

           right =r;

       }

      

       public void print() {

          System.out.println(key);

       }

   }

  

   private Node findNode(int val) {

       Node curr;

       curr = root;

      

       while (curr != null) {

           if (curr.key== val)

              break;

       }  

       return curr;

      

   }

  

   private void easyDelete(Node delNode, NodedelParent, Node delChild) {

   //delNode-Node to be deleted

   //delParent-parent of delNode

   //delChild-child of delNode

       if (delParent == null) {//deleting root node

           root =delChild;

       }

       else { //delNode is not root

           if (delNode== delParent.left)

              delParent.left = delChild;

           else

              delParent.right = delChild;

       }

   }

   private void twoChildrenDelete(Node curr) {

       Node is, isParent; //inordersuccessor and inorder successor’s parent

      

       is = curr.right;

       isParent = curr;

      

       while (is.left != null) { //findinorder successor to curr.

           isParent =is;

           is =is.left;

       }

       curr.key = is.key; //put inordersucessor’s value into node curr.

      easyDelete(is,isParent,is.right); //delete inorder successor node,which has no left child.

   }

  

   public void delete(int val) {

       Node curr = root;

       Node prev = null;

       while (curr != null &&curr.key != val) {

           prev =curr;

           if (val <curr.key)

              curr = curr.left;

           else

              curr = curr.right;

       }

      

       if (curr != null) { //keyfound

           if (curr.left== null)

              easyDelete(curr,prev, curr.right);

           else if(curr.right == null)

              easyDelete(curr,prev,curr.left);

           else

              twoChildrenDelete(curr);

       }

   }

}

Sample text file:

471121539810