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!

Recommended Answers

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.

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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.