Need help calculating the depth of left and right subbranches any binary tree

I have to write an AVL tree for my data structures course and am stuck on calculating the balance factor for a subtree so that I know where and how to rotate the tree.

Thanks, Eric

edit:

I know have to count to number of nodes in a binary tree.

private int countTotalNodes(AVLNode<T> start){

    AVLNode<T> current = start;

    if(current.getLeft() != null){
        return countTotalNodes(current.getLeft());
    }
    if(current.getRight() != null){
        return countTotalNodes(current.getRight());
开发者_如何学运维    }
    return 1;

} 

I think the usual implementation for an AVL tree stores the height of a node in the node itself and gets updated in insert, cut-and-link, operations. After those operations we then have to check if the height of the higher up nodes is still correct with something like this:

/**
 * Recursively updates heights starting with given node. 
 * If height of given node is already correct we know 
 * that we can stop.
 */
private void updateHeights(AvlNode<T> node){
    if(node == null) return;
    int heightLeft = node.left != null ? node.left.height : -1;
    int heightRight = node.right != null ? node.right.height : -1;
    int height = heightLeft > heightRight ? heightLeft + 1 : heightRight + 1;
    if(node.height != height){
        node.height = height;
        updateHeights(node.parent);
    }
}

That's always called on the parent of the highest changed node so to speak of. Ah good old times - implementing an AVL tree is a fun little project - good luck.. and test it thouroughly!

The usual approach is to add a balance factor field to the data structure of a tree node. Changes to the balance factor happen on inserts and deletes, and the changes propagate as rotations are made to keep things in balance. There's a nice explanation of this, with pseudocode, here.

Computing the balance at each insert or delete (instead of keeping the balance as a bit of extra bookkeeping at each node) makes those operations much more expensive.

Write the method to calculate the depth of a tree and then apply it to left and right sub-trees.

That's the beauty of the tree data structure: it's naturally self-similar and recursive.

Your counting function for number of nodes is wrong (except for very degenerated trees) - it counts either the left or the right subtree, but never both. Try to correct this first.

Then think about how you can use a similar algorithm to construct the depth.

But as said in other answers, don't use this for balancing your tree, as the performance penalty of this will be more than all the benefits of having a balanced tree. Instead store your depth in the nodes and think about when it needs to be adapted.