Getting a StackOverFlowError whenever I run my AVLTree.java code

Question

At the moment I'm trying to create an AVLTree to store data and and then print the data via in-order traversal. However I'm currently stuck trying to fix a StackOverflowError that seems to be occuring when I call my height() method.

I'm pretty sure the StackOverflowError is resulting from a bad recursion call on my height() method but I don't know why that bad recursion call is happening.

public class AVLTree<K,V> implements AVLTreeI<K,V> {
    class Node<K,V> {
        K key;
        V value;
        Node<K,V> leftChild;
        Node<K,V> rightChild;
        Node<K,V> parent;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            leftChild = rightChild = parent = null;
        }
    }
    private Node<K,V> root;
    private int currentSize;

    public AVLTree() {
        root = null;
        currentSize = 0;
    }

    public void add(K key, V value) {
        Node<K,V> node = new Node<K,V>(key, value);

        if (root == null) {
            root = node;
            currentSize++;
        }

        add(root, node);
    }

    private void add(Node<K,V> parent, Node<K,V> newNode) {
        if (((Comparable<K>)newNode.key).compareTo(parent.key) > 0) {

            if (parent.rightChild == null) {
                parent.rightChild = newNode;
                newNode.parent = parent;
                currentSize++;
            }
            else
                add(parent.rightChild, newNode);
        }
        else {
            if (parent.leftChild == null) {
                parent.leftChild = newNode;
                newNode.parent = parent;
                currentSize++;
            }
            else
                add(parent.leftChild, newNode);
        }
        checkBalance(newNode);
    } 

    public int height() {
        if (root == null)
            return 0;
        return height(root) - 1;
    }

    private int height(Node<K,V> node) {
        if (node == null)
            return 0;
        int leftHeight = height(node.leftChild) + 1;
        int rightHeight = height(node.rightChild) + 1;

        if (leftHeight > rightHeight)
            return leftHeight;
        return rightHeight;
    }

    public void checkBalance(Node<K,V> node) {
        if ((height(node.leftChild) - height(node.rightChild) > 1) || 
               (height(node.leftChild) - height(node.rightChild) < -1)) { 
                   rotate(node);
        }
        if (node.parent == null)
            return;
        checkBalance(node.parent);
    }

    public void rotate (Node<K,V> node) {
        if (height(node.leftChild) - height(node.rightChild) > 1) { 
            if (height(node.leftChild.leftChild) > 
                   height(node.leftChild.rightChild)) {
                       node = rightRotate(node);
            }
            else
                node = leftRightRotate(node);
        }
        else {
            if (height(node.rightChild.rightChild) > 
                   height(node.rightChild.leftChild)) {
                       node = leftRotate(node);
            }
        else 
            node = rightLeftRotate(node);
        }
        if (node.parent == null)
            root = node;    
    }

    public Node<K,V> leftRotate(Node<K,V> node) {
        Node<K,V> tmp = node.rightChild;
        node.rightChild = tmp.leftChild;
        tmp.leftChild = node;
        node.rightChild = tmp.parent;
        tmp.parent = node.parent;
        tmp.leftChild.parent = tmp;
        return tmp;
    }

    public Node<K,V> rightRotate(Node<K,V> node) {
        Node<K,V> tmp = node.leftChild;
        node.leftChild = tmp.rightChild;
        tmp.rightChild = node;
        node.leftChild = tmp.parent;
        tmp.parent = node.parent;
        tmp.rightChild.parent = tmp;
        return tmp;
    }

    public Node<K,V> rightLeftRotate(Node<K,V> node) {
        node.rightChild = rightRotate(node.rightChild);
        return leftRotate(node);
    }

    public Node<K,V> leftRightRotate(Node<K,V> node) {
        node.leftChild = leftRotate(node.leftChild);
        return rightRotate(node);
    }

Answer 1

Your problem is not the height() method (it seems reasonable), but the add() method:

public void add(K key, V value) {
    Node<K,V> node = new Node<K,V>(key, value);

    if (root == null) {
        root = node;
        currentSize++;
    }

    add(root, node);
}

You create a new Node and if the tree is empty you set the node as root node.

But then you go on and add the same node also as a subnode of the root node - which means that the node gets added as left subnode of itself. And it is this that leads to the infinite recursion.

Instead, your add method should add a node either as root node or as a subnode of the root node:

public void add(K key, V value) {
    Node<K,V> node = new Node<K,V>(key, value);

    if (root == null) {
        root = node;
        currentSize++;
    } else {
        add(root, node);
    }
}