Hi,

I am trying to create a method to check if a binary tree is an AVL tree without using the height method of the author's binary tree. This is my code USING the height:

public boolean isAVL(BinaryNode<AnyType> t)
{
int leftSubtreeHeight;
int rightSubtreeHeight;
if (t == null)
return true;
if (t.right != null && t.left != null) {
leftSubtreeHeight = height(t.left);
rightSubtreeHeight = height(t.right);
if (Math.abs(leftSubtreeHeight - rightSubtreeHeight) > 1 || Math.abs(rightSubtreeHeight - leftSubtreeHeight) > 1)
return false;

}
return true && isAVL(t.left) && isAVL(t.right);
}

This code works, but I need to find a way to find out if the tree is AVL balanced WITHOUT using the height method. I am boggled since the AVL definition is a tree that has subtrees that have a height difference of 0 or 1. Therefore, I cannot figure out how to create an AVL method without knowing the heights of the subtrees.

Thanks for any help!

Maybe I am overlooking the obvious, but why can't you use the depth property to help you test for an AVL tree?

All 4 Replies

Maybe I am overlooking the obvious, but why can't you use the depth property to help you test for an AVL tree?

Display the height method's content and how it traverses the tree.

public boolean isBalanced() {
boolean balanced = true;
isBalanced(root, balanced);
return balanced;
}

private void isBalanced(BinaryNode<T> node, boolean balanced) {
if(balanced)
{
int balanceFactor = getBalanceFactor(node);
if(balanceFactor == 1) { // Has children
int left = getBalanceFactor(node.left);
int right = getBalanceFactor(node.right);

int difference = Math.abs(left - right);

if(difference == 2)
balanced = false;
else {
isBalanced(node.left, balanced);
isBalanced(node.right, balanced);
}
}
}
}