CODEWITHSUNDEEP
recursionbinary-search-tree
Mr.Rabbit
Mr.Rabbit

Reputation: 101

Recursive to Iterative method for Binary Search Tree

I'm working on an assignment to get the height of the BST using an iterative method from an recursive method. Below will be the provided recursive code and my code. It is returning one greater than the actual height. For example, the height is suppose to 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;
}

Upvotes: 4

Views: 226

Answers (1)

Waseem Ahmad Naeem
Waseem Ahmad Naeem

Reputation: 890

Your Code is returning one more than actual height of Tree. I suggest you to use this code

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

Hope you understand your mistake.

Upvotes: 4

Related Questions