Question

Complete the Tree class within the following program: BalancingTrees.zip. There are three two classes and one driver in this program. You just need to complete or add the Tree class code.

In java please.

The code for tree class:

public class Tree {
   Node root;

   public Tree() {
       root = null;
   }
  
public int getHeight(Node node) {
if (node == null)
return 0;
return node.height;
}
  
public Node insertANDbalance(Node node, int element) {
  
   // base case
if (node == null)
return (new Node(element));
  
// inserting new elements into tree following Binary tree rules
if (element < node.key)
node.left = insertANDbalance(node.left, element);
else if (element > node.key)
node.right = insertANDbalance(node.right, element);
else
return node;
  
// updating heights of left and right
if (getHeight(node.left) > getHeight(node.right))
   node.height = 1 + getHeight(node.left);
else
   node.height = 1 + getHeight(node.right);
  
// balance tree as each new element is added to it
int balance;
if (node == null)
   balance = 0;
else
   balance = getHeight(node.left) - getHeight(node.right);
  
// left -> left
if (balance > 1 && element < node.left.key)
return rightRotate(node);
// right -> right
else if (balance < -1 && element > node.right.key)
return leftRotate(node);
// left -> right
else if (balance > 1 && element > node.left.key) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
// right -> left
else if (balance < -1 && element < node.right.key) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
  
return node;
}

   public Node rightRotate(Node root) {
       Node newRoot = root.left;
       Node Temp = newRoot.right;

       // Rotate
       newRoot.right = root;
       root.left = Temp;
      
       // Update
       if (getHeight(root.left) > getHeight(root.right))
           root.height = getHeight(root.left)+1;
       else
           root.height = getHeight(root.right)+1;

       if (getHeight(newRoot.left) > getHeight(newRoot.right) + 1)
           newRoot.height = getHeight(newRoot.left)+1;
       else
           newRoot.height = getHeight(newRoot.right)+1;
      
       return newRoot;
   }

   public Node leftRotate(Node root) {
       Node newRoot = root;
      
       // for students to complete for an assignment

       return newRoot;
   }
  

   public static void printTree(Node node, int n) {
   n += 5;

   // Base case
   if (node == null)
   return;
        
   printTree(node.right, n);
   for (int i = 5; i < n; i++)
   System.out.print(" ");
   System.out.println(node.key);
   printTree(node.left, n);
   }
}

The code for node class:

public class Node {
   protected int key, height;
   protected Node left, right;

   public Node(int item) {
       key = item;
       height = 1;
       left = right = null;
   }
}

The driver:

public class TreeDriver{
   public static void main(String[] args) {
       Tree tree = new Tree();

       /* 6
       * / \
       * 2 7
       * / \   
       * 1 4   
       * / \   
       * 3 5
       *   
       */
       tree.root = tree.insertANDbalance(tree.root, 6);
tree.root = tree.insertANDbalance(tree.root, 2);
tree.root = tree.insertANDbalance(tree.root, 1);
tree.root = tree.insertANDbalance(tree.root, 4);
tree.root = tree.insertANDbalance(tree.root, 3);
tree.root = tree.insertANDbalance(tree.root, 5);
tree.root = tree.insertANDbalance(tree.root, 7);
      
tree.printTree(tree.root, 0);
      
   }
}

Answer 1

Program Screenshot for Indentation Reference:

Program code to copy:

public class Tree {
    Node root;

    public Tree() {
        root = null;
    }

    public int getHeight(Node node) {
        if (node == null)
            return 0;
        return node.height;
    }

    public Node insertANDbalance(Node node, int element) {

        // base case
        if (node == null)
            return (new Node(element));

        // inserting new elements into tree following Binary tree rules
        if (element < node.key)
            node.left = insertANDbalance(node.left, element);
        else if (element > node.key)
            node.right = insertANDbalance(node.right, element);
        else
            return node;

        // updating heights of left and right
        if (getHeight(node.left) > getHeight(node.right))
            node.height = 1 + getHeight(node.left);
        else
            node.height = 1 + getHeight(node.right);

        // balance tree as each new element is added to it
        int balance;
        if (node == null)
            balance = 0;
        else
            balance = getHeight(node.left) - getHeight(node.right);

        // left -> left
        if (balance > 1 && element < node.left.key)
            return rightRotate(node);
        // right -> right
        else if (balance < -1 && element > node.right.key)
            return leftRotate(node);
        // left -> right
        else if (balance > 1 && element > node.left.key) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }
        // right -> left
        else if (balance < -1 && element < node.right.key) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

        return node;
    }

    public Node rightRotate(Node root) {
        Node newRoot = root.left;
        Node Temp = newRoot.right;

        // Rotate
        newRoot.right = root;
        root.left = Temp;

        // Update
        if (getHeight(root.left) > getHeight(root.right))
            root.height = getHeight(root.left) + 1;
        else
            root.height = getHeight(root.right) + 1;

        if (getHeight(newRoot.left) > getHeight(newRoot.right) + 1)
            newRoot.height = getHeight(newRoot.left) + 1;
        else
            newRoot.height = getHeight(newRoot.right) + 1;

        return newRoot;
    }

    public Node leftRotate(Node root) {
        Node newRoot = root.right;

        Node Temp = newRoot.left;

        // Rotate
        newRoot.left = root;
        root.right = Temp;

        // Update
        if (getHeight(root.left) > getHeight(root.right))
            root.height = getHeight(root.left) + 1;
        else
            root.height = getHeight(root.right) + 1;

        if (getHeight(newRoot.left) > getHeight(newRoot.right) + 1)
            newRoot.height = getHeight(newRoot.left) + 1;
        else
            newRoot.height = getHeight(newRoot.right) + 1;

        // return new root
        return newRoot;
    }

    public static void printTree(Node node, int n) {
        n += 5;

        // Base case
        if (node == null)
            return;

        printTree(node.right, n);
        for (int i = 5; i < n; i++)
            System.out.print(" ");
        System.out.println(node.key);
        printTree(node.left, n);
    }
}

Sample Output:

This created a balanced tree: