Solved

# Semi - balanced binary tree.

Posted on 2011-10-22
938 Views

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

0
Question by:gudni12345

LVL 84

Expert Comment

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

LVL 6

Accepted Solution

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

## Featured Post

### Suggested Solutions

One of Google's most recent algorithm changes affecting local searches is entitled "The Pigeon Update." This update has dramatically enhanced search inquires for the keyword "Yelp." Google searches with the word "Yelp" included will now yield Yelp a…
Prime numbers are natural numbers greater than 1 that have only two divisors (the number itself and 1). By “divisible” we mean dividend % divisor = 0 (% indicates MODULAR. It gives the reminder of a division operation). We’ll follow multiple approac…
Need more eyes on your posted question? Go ahead and follow the quick steps in this video to learn how to Request Attention to your question. *Log into your Experts Exchange account *Find the question you want to Request Attention for *Go to the e…
Migrating to Microsoft Office 365 is becoming increasingly popular for organizations both large and small. If you have made the leap to Microsoft’s cloud platform, you know that you will need to create a corporate email signature for your Office 365…