Balanced Binary Tree Problem

Problem description:
level: medium

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Given binary tree A={3,9,20,#,#,15,7}, B={3,#,20,15,7}
The binary tree A is a height-balanced binary tree, but B is not.


consider a node, if left is balanced, right is balanced, and left, right nodes height difference < 2, then the node is balanced

Another thought:
if a node is not balanced, then its height set to -1
else return it is real height

Using Divide & Conquer, we can get the height to decide if it is a balanced tree

Time complex: O(n)

Share on FacebookShare on Google+Tweet about this on TwitterShare on LinkedInShare on RedditShare on StumbleUponEmail this to someoneShare on TumblrDigg this

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">