CODEWITHSUNDEEP
java
cook cook
cook cook

Reputation: 305

Need help on Binary Tree height

This is a question from grade 12 Binary tree assignment. It wants a method for BTree class to return the height of the tree. I assume when there's one node in the tree the height is 0, not sure about that, i'll ask my teacher today.

But anyways, here's my code, i have no idea what's wrong with it.

public int height(){
    if(root == null){
        return -1;
    }
    return height(root, 0, 0);
}
public int height(BNode branch, int depth, int ans){
    if(depth>ans){
        ans=depth;
    }
    if(branch.getLeft()!=null){
        depth+=1;
        return height(branch.getLeft(), depth, ans);
    }
    else if(branch.getRight()!=null){
        depth+=1;
        return height(branch.getRight(), depth, ans);
    }
    return ans;
}

This is the testing class:

    BTree bTree = new BTree();
    bTree.add(50);
    bTree.add(60);
    bTree.add(40);
    bTree.add(35);
    bTree.add(55);
    bTree.add(45);
    bTree.add(51);
    bTree.display();
    System.out.println(bTree.height());

This tree should have a height of 3, but it's returning:35 40 45 50 51 55 60 2

Any help would be appreciated, thanks.

Upvotes: 0

Views: 139

Answers (2)

Osama Javed
Osama Javed

Reputation: 1442

just a hint. When traversing over a tree to do some calculations you need to recursively handle both the sub-trees.

So height of any non-null given tree node should be 

max( (  height of left sub tree) , (height of right  sub tree)) + 1

as mentioned in other answers your traversal is not correct.

if a node is null then its height is 0.

similarly the size of any non null node would be sizeof(left)+sizeof(right)+1 etc

Upvotes: 0

James
James

Reputation: 8586

You favor your left node over your right node. The height of a node should be: 

MAX(height(left), height(right)) + 1

But instead you're effectively saying instead:

if (left)
   return height(left) + 1
else if (right) 
   return height(right) + 1

So if a node has a short left leg and a long right, you get the wrong answer.

Upvotes: 2

Related Questions