Member Avatar for Gaiety

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
  • 131 Views
  • 7 Hours Discussion Span
  • Latest Post Latest Post by Barefootsanders

Recommended Answers

All 2 Replies

Member Avatar for Nick Evan

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 because: n/a
Member Avatar for Barefootsanders

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 because: n/a
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.