0

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!

5
Contributors
4
Replies
11
Views
8 Years
Discussion Span
Last Post by JamesCherrill
0

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

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 by JamesCherrill

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.