# Leetcode: 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 everynode never differ by more than 1.

```public boolean isBalanced(TreeNode root) {
// Start typing your Java solution below
// DO NOT write main() function
if(isBalancedHelper(root)==-1){
return false;
}else{
return true;
}
}

//return -1 if the two subtrees of this node is unbalanced
//return the height of this node otherwise
public int isBalancedHelper(TreeNode node){
if(node==null){
return 0;
}else{
int leftHeight = isBalancedHelper(node.left);
int rightHeight = isBalancedHelper(node.right);
if(leftHeight==-1 || rightHeight==-1){
return -1;
}
if(Math.abs(leftHeight-rightHeight)<=1){
return Math.max(leftHeight,rightHeight)+1;
}else{
return -1;
}
}
}```

Running time is O(n) since all the nodes are visited only once.

Share

Given two binary strings, return their sum (also a binary string).

For example,
a = `"11"`
b = `"1"`
Return `"100"`.

```public String addBinary(String a, String b) {
// Start typing your Java solution below
// DO NOT write main() function
int carry = 0;
String sumStr = "";
int i=a.length()-1;
int j=b.length()-1;
while(i>=0 || j>=0){
int bitSum =0;
if(i>=0 && j>=0){
bitSum= Integer.parseInt(a.substring(i,i+1))+Integer.parseInt(b.substring(j,j+1)) + carry;
i--;
j--;
}else if(i>=0){
bitSum= Integer.parseInt(a.substring(i,i+1))+carry;
i--;
}else{
bitSum= Integer.parseInt(b.substring(j,j+1)) + carry;
j--;
}
carry = bitSum/2;
int bit = bitSum%2;
sumStr = bit+sumStr;
}
if(carry==1){
sumStr = carry+sumStr;
}
return sumStr;
}```