Binary search tree

I wonder if anyone can help me rework this approach to determine the height of the binary search tree. So far, my code is as follows.

public int findHeight(){
    if(this.isEmpty()){
        return 0;
    }
    else{
        TreeNode<T> node = root;
        return findHeight(node);
    }
}
private int findHeight(TreeNode<T> aNode){
    int heightLeft = 0;
    int heightRight = 0;
    if(aNode.left!=null)
        heightLeft = findHeight(aNode.left);
    if(aNode.right!=null)
        heightRight = findHeight(aNode.right);
    if(heightLeft > heightRight){
        return heightLeft+1;
    }
    else{
        return heightRight+1;
    }
}

But the answer I get is one higher than my actual height. However, after reading this source, we know that removing +1 from the return statement reduces the actual height by 1. I'm still trying to figure out the recursion using this BST. I'd appreciate your help.

java

2023-02-23 07:44

1 Answers

private int findHeight(TreeNode<T> aNode){
    return findHeight(aNode, -1);
}

private int findHeight(TreeNode<T> aNode, int depth){
    if(aNode == null){ return depth; }
    return Math.max(
        findHeight(aNode.left, depth + 1),
        findHeight(aNode.right, depth + 1)
    );
}

Do you want this kind of feeling?

2023-02-23 10:09

If you have any answers or tips

Popular Tags

python x 4647

android x 1593

java x 1494

javascript x 1427

c x 927

c++ x 878

ruby-on-rails x 696

php x 692

python3 x 685

html x 656