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!

Here is your answer. Avl tree is a Balanced Binary 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);
                }
            }
        }
    }

A bizarre answer...
1. This thread has been dead for 3 years, it's a bit late to answer ir.
2. That method doesn't return anything. In fact it has no output of any sort at all. It's completely useless.

Edited 2 Years Ago by JamesCherrill

This article has been dead for over six months. Start a new discussion instead.