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