# Semi - balanced binary tree.

How do I write a recursive algorithm that checks whether a binary search
tree is semi-balanced.

###### Who is Participating?

Commented:
Specification: A well-formed binary tree is said to be "height-balanced" if (1) it is empty, or (2) its left and right children are height-balanced and the height of the left tree is within 1 of the height of the right tree.

See more details in the source I quoted..

``````IsHeightBalanced(tree)
return (tree is empty) or
(IsHeightBalanced(tree.left) and
IsHeightBalanced(tree.right) and
abs(Height(tree.left) - Height(tree.right)) <= 1)
``````

Source: http://stackoverflow.com/questions/742844/how-to-determine-if-binary-tree-is-balanced
0

Commented:
balancedheight(node)::=
if node.isleaf then
return 1
elseif balancedheight(node.left)>0 and balancedheight(node.rignt) > 0 and abs(balancedheight(node.left)-balancedheight(node.rignt)) <=1 then
return 1+max(balancedheight(node.left),balancedheight(node.rignt)
else
return 0

0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.