# Balanced Binary Tree

Nov 13, 2017

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.

bool isBalanced(TreeNode* root) {
int h = 0;
return isBalanced(root,h);
}
bool isBalanced(TreeNode *root,int &height) {
if (root == nullptr) { height = 0; return true; }
int left,right;
if (!isBalanced(root->left,left) || !isBalanced(root->right,right))
return false;

if (abs(left - right) > 1) return false;

height = max(left,right) + 1;
return true;
}


class Solution:
def isBalanced(self,root):
"""
:type root: TreeNode
:rtype: bool
"""
res,height = self.isBalancedRec(root)
return res

def isBalancedRec(self, root):
"""
:type root: TreeNode
:rtype: bool,int
"""
if root is None:
return True,0

leftRes,leftH = self.isBalancedRec(root.left)
rightRes,rightH = self.isBalancedRec(root.right)

if leftRes == False or rightRes == False:
return False,max(leftH,rightH)
else:
return abs(leftH-rightH) <= 1,max(leftH,rightH)+1

LeetCodeLeetCodeTree

Symmetric Tree

Climbing Stairs