Semi - balanced binary tree.


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


gudni12345Asked:
Who is Participating?
 
theKashyapCommented:
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)

Open in new window


Source: http://stackoverflow.com/questions/742844/how-to-determine-if-binary-tree-is-balanced
0
 
ozoCommented:
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.

All Courses

From novice to tech pro — start learning today.