Semi - balanced binary tree.

Posted on 2011-10-22
Last Modified: 2012-06-27

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

Question by:gudni12345
    LVL 84

    Expert Comment

    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)
      return 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..

        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


    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone.

    Featured Post

    Looking for New Ways to Advertise?

    Engage with tech pros in our community with native advertising, as a Vendor Expert, and more.

    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…

    761 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    8 Experts available now in Live!

    Get 1:1 Help Now