Recursive Iteration Method for Binary Search Tree

Question

I am working on an assignment to get the height of a BST using an iterative method from a recursive method. Below will be the provided recursive code and my code. It returns one greater than the actual height. For example, the height should be 4, but it returns 5.

//Provided code 
public  int getHeight() {
    return getHeight(root);
}

private int getHeight(Node node) {
    if (node==null) {
        return -1;
    } else {
        int leftHeight = getHeight(node.left);
        int rightHeight = getHeight(node.right);
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

//my code
public int getHeightI() {
    return getHeightI(root);
}

private int getHeightI(Node node) {
    Node curr = node;
    int leftHeight = 0;
    int rightHeight = 0;
    if (curr!=null) {
        while (curr.left!=null) {
            leftHeight++; 
            curr = curr.left;
        } 
        while (curr.right!=null) {
            rightHeight++; 
            curr = curr.right; 
        }
    }   
    return Math.max(leftHeight, rightHeight)+1;
}

Answer 1

In your code, another actual tree height is returned. I suggest you use this code

int height(tree* root)
{
if(!root)
{ return -1;
}
else{
return __max(root->left,root->right);
}

I hope you understand your mistake.