Recursive to Iterative method for Binary Search Tree

Question

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;
}

Possible duplicate of Finding max depth of binary tree without recursion — Tim Biegeleisen
– Tim Biegeleisen, Commented Nov 27, 2015 at 5:32
The reason your current code is off by 1 is because you are adding 1 to the return statement. But your algorithm itself is also wrong. Please see the code in the link above. — Tim Biegeleisen
– Tim Biegeleisen, Commented Nov 27, 2015 at 5:33
@TimBiegeleisen Thanks for the link. It's full of useful stack implementations of finding the depth. However, I was looking for a way to implement it without using stacks. And yes, if I delete the +1 for the return statement it works, but I know that is not the correct way to fix this method. — Mr.Rabbit
– Mr.Rabbit, Commented Nov 27, 2015 at 6:09
You are going to need to use some sort of stack-esque data structure if you want to do this iteratively. Actually, when you solve it recursively, you are still using a stack: the function call stack. Really, if you examine the machine code from both methods, they should look very similar. — Tim Biegeleisen
– Tim Biegeleisen, Commented Nov 27, 2015 at 6:10

Waseem Ahmad Naeem · Accepted Answer · 2015-11-29 07:53:17Z

4

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.

answered Nov 29, 2015 at 7:53

Waseem Ahmad Naeem

8901 gold badge10 silver badges22 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Recursive to Iterative method for Binary Search Tree

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related