Can't get Height from AVLTree in JAVA

Question

I am making an AVL Tree as an assignment.
I am having problems when getting height of a tree.
Something wrong with my code all methods are working properly except height method.
When i call getHeight() it shows me that: Zero(0) it has to be 6 or 7.
I could not find where i did wrong.

class AVLNode<K extends Comparable<K>, V extends K> {
    AVLNode<K, V> leftChild, rightChild;
    K key;
    V value;
    int avlNodeHeight;

    /* Constructor */
    public AVLNode() {
        leftChild = null;
        rightChild = null;
        key = null;
        avlNodeHeight = 0;
    }

    /* Constructor */
    public AVLNode(K n) {
        leftChild = null;
        rightChild = null;
        key = n;
        avlNodeHeight = 0;
    }

    /* Constructor */

    public AVLNode(K key, V value) {
        leftChild = null;
        rightChild = null;
        this.key = key;
        this.value = value;
        avlNodeHeight = 0;
    }

    public void setLeftChild(AVLNode<K, V> leftChild) {
        this.leftChild = leftChild;
    }

    public AVLNode<K, V> getLeftChild() {
        return leftChild;
    }

    public void setRightChild(AVLNode<K, V> rightChild) {
        this.rightChild = rightChild;
    }

    public AVLNode<K, V> getRightChild() {
        return rightChild;
    }

    public void setKey(K key) {
        this.key = key;
    }

    public K getKey() {
        return key;
    }

    public void setValue(V value) {
        this.value = value;
    }

    public V getValue() {
        return value;
    }

    public void setHeight(int height) {
        avlNodeHeight = height;
    }

    public int getHeight() {
        return avlNodeHeight;
    }

}

/* Class AVLTree */
class AVLTree<K extends Comparable<K>, V extends K> {
    AVLNode<K, V> root;

    /* Constructor */
    public AVLTree() {
        root = null;
    }

    /* Function to check if tree is empty */
    public boolean isEmpty() {
        return root == null;
    }

    /* Make the tree logically empty */
    public void makeEmpty() {
        root = null;
    }

    /* Function to get height of node */
    protected int height(AVLNode<K, V> root) {
        return root == null ? -1 : root.avlNodeHeight;
    }

    /* Function to max of left/right node */
    protected int max(int value1, int value2) {
        return Math.max(value1, value2);
    }

    protected K getSmallestValue(AVLNode<K, V> n) {
        if (n.getLeftChild() == null)
            return n.getKey();
        return getSmallestValue(n.getLeftChild());
    }

    /* Function to insert data */
    public void insert(K key, V value) {
        root = insert(key, value, root);
    }

    /* Function to insert data recursively */
    protected AVLNode<K, V> insert(K key, V value, AVLNode<K, V> root) {
        if (root == null)
            root = new AVLNode<K, V>(key, value);
        else if (key.compareTo(root.getKey()) < 0) {
            root.leftChild = insert(key, value, root.leftChild);

            if (height(root.leftChild) - height(root.rightChild) == 2)
                if (key.compareTo(root.getLeftChild().getKey()) < 0)
                    root = rotateLeftChild(root);
                else
                    root = doubleRotateLeftChild(root);
        } else if (key.compareTo(root.getKey()) > 0) {

            root.rightChild = insert(key, value, root.rightChild);
            if (height(root.rightChild) - height(root.leftChild) == 2)
                if (key.compareTo(root.rightChild.getKey()) > 0)
                    root = rotateRightChild(root);
                else
                    root = doubleRotateRightChild(root);
        } else if (root.getKey().equals(key)) {
            root.setValue(value);
            return root;
        } else
            root.avlNodeHeight = max(height(root.leftChild),
                    height(root.rightChild)) + 1;
        return root;
    }

    public void delete(K key) {
        root = delete(root, key);
    }

    protected AVLNode<K, V> delete(AVLNode<K, V> n, K key) {
        if (n == null)
            return null;
        if (key.compareTo(n.getKey()) < 0) {
            n.setLeftChild(delete(n.getLeftChild(), key));
            return balance(n);
        }
        else if (key.compareTo(n.getKey()) > 0) {
            n.setRightChild(delete(n.getRightChild(), key));
            return balance(n); // Deleting may have unbalanced tree.
        }
        // Else, we found it! Remove n.
        else {
            // 0 children
            if (n.getLeftChild() == null && n.getRightChild() == null)
                return null;
            // 1 child - guaranteed to be balanced.
            if (n.getLeftChild() == null)
                return n.getRightChild();
            if (n.getRightChild() == null)
                return n.getLeftChild();

            // 2 children - deleting may have unbalanced tree.

            K smallestKey = getSmallestValue(n.getRightChild());
            n.setKey(smallestKey);
            n.setRightChild(delete(n.getRightChild(), smallestKey));
            return balance(n);

        }
    }

    /* Functions to count number of nodes */
    public int countNodes() {
        return getNodesCount(root);
    }

    protected int getNodesCount(AVLNode<K, V> root) {

        if (root != null) {
            int counter = 1;
            counter += getNodesCount(root.leftChild);
            counter += getNodesCount(root.rightChild);
            return counter;
        } else
            return 0;

    }

    /* Functions to search for an element */
    public boolean search(K key) {
        return search(root, key);
    }

    protected boolean search(AVLNode<K, V> root, K key) {
        boolean check = false;

        while ((root != null) && !check) {
            K rootValue = root.key;

            if (key.compareTo(rootValue) > 0)
                root = root.rightChild;
            else if (key.compareTo(rootValue) < 0)
                root = root.leftChild;
            else {
                check = true;
                break;
            }
            check = search(root, key);
        }
        return check;
    }

    protected AVLNode<K, V> balance(AVLNode<K, V> root) {
        root.setHeight(1 + Math.max(height(root.getLeftChild()),
                height(root.getRightChild())));
        return root;
    }

    /* Rotate binary tree node with left child */
    protected AVLNode<K, V> rotateLeftChild(AVLNode<K, V> node) {
        AVLNode<K, V> avlNode = node.leftChild;

        node.leftChild = avlNode.rightChild;

        avlNode.rightChild = node;

        node.avlNodeHeight = max(height(node.leftChild),
                height(node.rightChild)) + 1;

        avlNode.avlNodeHeight = max(height(avlNode.leftChild),
                node.avlNodeHeight) + 1;

        return avlNode;
    }

    /* Rotate binary tree node with right child */
    protected AVLNode<K, V> rotateRightChild(AVLNode<K, V> node) {
        AVLNode<K, V> avlNode = node.rightChild;

        node.rightChild = avlNode.leftChild;

        avlNode.leftChild = node;

        node.avlNodeHeight = max(height(node.leftChild),
                height(node.rightChild)) + 1;

        avlNode.avlNodeHeight = max(height(avlNode.rightChild),
                node.avlNodeHeight) + 1;
        return avlNode;
    }

    protected AVLNode<K, V> doubleRotateLeftChild(AVLNode<K, V> node) {
        node.leftChild = rotateRightChild(node.leftChild);
        return rotateLeftChild(node);
    }

    protected AVLNode<K, V> doubleRotateRightChild(AVLNode<K, V> node) {
        node.rightChild = rotateLeftChild(node.rightChild);
        return rotateRightChild(node);
    }

}

public class AVLTreeTest {
    public static void main(String[] args) {
        AVLTree<Integer, Integer> avlt = new AVLTree<>();

        for (int i = 0; i < 1200; i++)
            avlt.insert(i, i + 5);

        System.out.println("Height of AVL TREE: " + avlt.root.getHeight());
    }
}

Answer 1

In insert(), the first and second else if never update the height.

I think you want to move

    root.avlNodeHeight = max(height(root.leftChild),
            height(root.rightChild)) + 1;

out of the else.

There could be other bugs...

Answer 2

if you are using the below code height method has to be recursive to get the height, but you have implemented in balance method i guess which is wrong.

max(height(root.leftChild), height(root.rightChild)) + 1;

or else you have to setHeight(AVLNode) every time you insert or delete.