Balanced Binary Tree

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

An example of a height-balanced tree. A height-balanced tree is a tree whose subtrees differ in height by no more than one and the subtrees are height-balanced, too.

C++:
01 bool isBalan(TreeNode *root, int& hight)
02  {
03      if(root==NULL){
04          hight=0;
05          return true;
06      }
07      int left_hight;
08      int right_hight;
09      if(isBalan(root->left,left_hight)==false) return false;
10      if(isBalan(root->right,right_hight)==false) return false;
11      if((left_hight>right_hight+1)||(right_hight>left_hight+1))
12        return false;
13      hight=left_hight>right_hight?left_hight+1:right_hight+1;
14      return true;
15  }
16 
17  bool isBalanced(TreeNode *root)
18  {
19      int high;
20      return isBalan(root,high);
21  }
Advertisements
This entry was posted in Recursive, Tree. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s