• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 1045
  • Last Modified:

Semi - balanced binary tree.


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


0
gudni12345
Asked:
gudni12345
1 Solution
 
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
 
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

Featured Post

Free Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now