Solution to LeetCode Problems: Balanced Binary Tree

Balanced Binary Tree

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.

Thoughts:
When a tree node is considered as "balanced", the left and the right leaf nodes are both "balanced", and the difference between height of left and right leaf is at most 1. A recursive procedure can then be designed.

Also worthy to mention, there are several common used self-balanced binary tree alogorithms: AVL Tree and RB Tree.

Solution:

1. /** 
2.  * Definition for binary tree 
3.  * struct TreeNode { 
4.  *     int val; 
5.  *     TreeNode *left; 
6.  *     TreeNode *right; 
7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 
8.  * }; 
9.  */  
10. class Solution {  
11. public:  
12.     pair<bool, int> TraverseProc(const TreeNode* node)  
13.     {  
14.         if (node == nullptr)  
15.             return make_pair(true, 0);  
16.               
17.         // check left branch  
18.         pair<bool, int> left_balance=TraverseProc(node->left);  
19.         if (!left_balance.first) return make_pair(false, 0);  
20.           
21.         // check right branch  
22.         pair<bool, int> right_balance=TraverseProc(node->right);  
23.         if (!right_balance.first) return make_pair(false, 0);  
24.           
25.         // check the current node  
26.         int balance_factor = left_balance.second - right_balance.second;  
27.         if (balance_factor>1 || balance_factor<-1)  
28.             return make_pair(false, 0);  
29.         else  
30.             return make_pair(true, max(left_balance.second, right_balance.second)+1);  
31.     }  
32.   
33.     bool isBalanced(TreeNode *root) {  
34.         // Note: The Solution object is instantiated only once and is reused by each test case.  
35.         return TraverseProc(root).first;  
36.     }  
37. };