Hi,
Please suggest me how to check a given tree is balanced using the height of tree.
we need to use the avl tree concept.

i.e, the difference between height of any left or right subtree is atmost 1.

i have written the code for inserting the node, but this one i can't understand .

3
Contributors
2
Replies
4
Views
7 Years
Discussion Span
Last Post by Barefootsanders

Can't explain it as good as Narue does here, so you should take an hour or two to read the article. Everything will be clear afterwards :)

Edited by Nick Evan: n/a

If you understand the concepts and have written the insert function, then this should not be all that difficult to understand. Just for reference:

In an AVL tree, the heights of the two child subtrees of any node differ by at most one

So one solution would be to write a function that takes a node, at any given point in the tree, and can calculate its height (might involve recursion depending on how you determine it). Then you can pass child of the root to this function and determine if its a proper AVL tree or not.

Below is some scrappy pseudocode:
if heightLeftSubTree - heightRightSubTree is between -1 and 1
--this tree is an AVL tree
else
--this tree is NOT an AVL tree
end

Hope that helps (without giving to much away :) )

Edited by Barefootsanders: n/a

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.