The rotateRight method and rotateLeft methods need to be applied properly in the add method. But I do not know how exactly to apply it. The output is not correct for PostOrder Traversal for the given array.

import static java.lang.Integer.max;
import java.util.Arrays;

public class AVLTree {

    private Node root;

     /**
     * default constructor initializes an empty tree.
     */
    public AVLTree() {
        root = null;
    }

    /**
     * overloaded constructor builds an AVL tree using the array values
     * @param values
     */
    public AVLTree(Comparable[] values) {
        System.out.println("The given array: " + Arrays.toString(values));
        for (Comparable value : values) {
            add(value);
        }
    }

    /**
     * adds an object into the AVL tree into a position that maintains the BST
     * property. Performs the necessary rotations to re-balance any imbalances.
     * @param e 
     */
    public void add(Comparable e) {       
      Node newNode = new Node();
      newNode.data = e;
      newNode.left = null;
      newNode.right = null;
      if (root == null) 
      { 
          root = newNode; 
      }
      else 
      { 
          root.addNode(newNode);
      }




      //Left Left Case
      if  (diff() > 1 && newNode.left.data.compareTo(e) == -1){
            rotateRight(newNode); 
      }
      // Right Right Case 
        if  (diff() < -1 && newNode.right.data.compareTo(e) == 1){
            rotateLeft(newNode.right);
        }

        // Left Right Case 
        if  (diff() > 1 && newNode.left.data.compareTo(e) == 1) { 
            rotateLeft(newNode.left); 
            rotateRight(newNode); 
        } 

        // Right Left Case 
        if  (diff() < -1 && newNode.right.data.compareTo(e) == -1) { 
            rotateRight(newNode.right); 
            rotateLeft(newNode); 
        }

    }

    /**
     * Procedure rightRotate(N) 
     * i. Define SR the subtree rooted an N.left.right
     * ii. Make N the right child of N.left 
     * iii. Make the root of SR the left child of N
     * @param n is the parent
     */
    void rotateRight(Node n) {
        Node temp = n.left;
        Node temp2 = temp.right;
        n.right = n;
        n.left = temp2;

    }

    /**
     * Procedure leftRotate(N) 
     * i. Define SL the subtree rooted an N.right.left
     * ii. Make N the left child of N.right 
     * iii. Make the root of SL the right child of N
     * @param n
     */
    void rotateLeft(Node n) { 
        Node temp = n.right;
        Node temp2 = temp.left;
        n.left = n;
        n.right = temp2;
    }
    /**
     * This method calculates the difference at each node.
     * @param n
     * @return - the difference between left subtree and right tree is returned.
     */
    int diff(Node n) {
        int left_height;
        int right_height;
        left_height = height(n.left);
        right_height = height(n.right);
        int difference = left_height - right_height;
        return difference;
    }

    int diff() {
        return diff(root);
    }
    /**
     * This method calculates the height based on node
     * @param n
     * @return - This returns the height of the tree
     */
    int height(Node n) {
        if (n == null) {
            return -1;
        }
        int height = 1 + max(height(n.right), height(n.left));
        return height;
    }

    int height() {
        return height(root);
    }
    /**
     * This method finds the node based on the given user node,
     * @param value
     * @return  - if is it found will return "was found" (true) else, "was not found" (found)
     */
    public boolean find(Comparable value) {
        Node current = root;
        while (current != null) {
            int d = current.data.compareTo(value);
            if (d == 0) {
                System.out.println(value + " was found.");
                return true;
            } else if (d > 0) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
        System.out.println(value + " was not found.");
        return false;
    }

    /**
     * returns a string representation of the tree. Elements are listed using
     * post-order traversal. Algorithm Postorder(tree) 1. Traverse the left 2.
     * Traverse the right 3. Visit the root.
     * @return
     */
    @Override
    public String toString() {

        String temp;
        if (root == null) {
            return "Tree is empty";
        } else {
            temp = "(" + root.data;
        }
        if (root.left.data != null && root.right.data != null) {
            temp = temp + " " + root.left.data.toString() + " " + root.right.data.toString();
        }
        return temp = temp + ")";
    }
    /**
     * This method prints the AVL tree in Post Order Traversal method.
     * @param node 
     */
    void printPostOrder(Node node) {
        if (node != null) {
            printPostOrder(node.left);
            printPostOrder(node.right);

            System.out.print(node.data + " ");
        }
    }

    void printPostOrder() {
        printPostOrder(root);
    }

    class Node {
        public Node parent;
        public Comparable data;
        public Node left;
        public Node right;

        /**
         * Inserts a new node as a descendant of this node.
         * @param newNode the node to insert
         */
        public void addNode(Node newNode) {
            int comp = newNode.data.compareTo(data);
            if (comp < 0) {
                if (left == null) {
                    left = newNode;
                } else {
                    newNode.parent = this;
                    left.addNode(newNode);
                }
            } else if (comp > 0) {
                if (right == null) {
                    newNode.parent = this;
                    right = newNode;
                } else {
                    newNode.parent = right;
                    right.addNode(newNode);
                }
            }
        }
    }

    public static void main(String[] args) {

        Integer[] treeArray = {14, 17, 11, 7, 53, 4, 13, 8};
        AVLTree treeA = new AVLTree(treeArray);

        System.out.println("\nThe tree - Post Order Traversal: ");
        treeA.printPostOrder();
        System.out.println("\nheight of the tree: " + treeA.height());
        System.out.println();

        System.out.println("Finding values 1 and 4 in the tree...");
        treeA.find(1);
        treeA.find(4);


    }
}

The correct output should be for PostOrder traversal for AVL Trees, 4, 8, 13, 11, 7, 53, 17, 14

0 Answers