# Java solution based on height, check left and right node in every recursion to avoid further useless search

• ``````public boolean isBalanced(TreeNode root) {
if(root==null){
return true;
}
return height(root)!=-1;

}
public int height(TreeNode node){
if(node==null){
return 0;
}
int lH=height(node.left);
if(lH==-1){
return -1;
}
int rH=height(node.right);
if(rH==-1){
return -1;
}
if(lH-rH<-1 || lH-rH>1){
return -1;
}
return Math.max(lH,rH)+1;
}``````

• Great code, but the first

`````` if(root==null){
return true;
}
``````

is unnecessary because it will be checked within the height function.

• This post is deleted!

• Great! Much better than my answer which cost O(N2)...

• My code is more concise

``````    /**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isBalanced(TreeNode root) {
return getDepth(root)!=-1;
}

public int getDepth(TreeNode root){
if(root==null){
return 0;
}
int left = getDepth(root.left);
if(left!=-1){
int right = getDepth(root.right);
if(right!=-1){
return Math.abs(left-right)<=1?1+Math.max(left,right):-1;
}
}
return -1;
}
}
``````

• This post is deleted!

• Good idea using -1 as unbalanced signal alternatively you could use a reference parameter or pointer or whatever you language offers. Here's a C# version

``````    public bool IsBalanced(TreeNode root)
{
bool result = true;
int depth = Depth(root, ref result);
return result;
}

public int Depth(TreeNode node, ref bool result)
{
if (result == false || node == null) return 0;
int leftDepth = Depth(node.left, ref result);
int rightDepth = Depth(node.right, ref result);

if (leftDepth - rightDepth > 1 || leftDepth - rightDepth < -1)
{
result = false;
}

return 1 + Math.Max(leftDepth, rightDepth);
}
``````

• good solution using -1 as a boolean marker!

• Hey @mingyuan, your solution is really elegant. However, I am not able to understand why my solution's logic is incorrect. Do you have any idea? Here is the code:

``````public class Solution {
public boolean isBalanced(TreeNode root) {
if(root==null) return true;
return     Math.abs(h(root.left) - h(root.right))<=1 ;

}

public int h(TreeNode root){
if(root==null) return 0;
return (1 + Math.max(h(root.left),h(root.right)));
}
}
``````

• This post is deleted!

• return Math.abs(h(root.left) - h(root.right))<=1 && isBalanced(root.left) && isBalacend(root.right)

• ``````public class Solution {

boolean flag;
public boolean isBalanced(TreeNode root) {
flag = true;
judge(root);
return flag;
}

public int judge(TreeNode tNode){
if(tNode == null) return 0;
int leftLen = 1 + judge(tNode.left);
int rightLen = 1 + judge(tNode.right);
if(Math.abs(rightLen - leftLen) > 1){
flag = false;
return -1;
}
return leftLen > rightLen ? leftLen : rightLen;
}
}
``````

• @Eva001 why are you returning -1 after setting flag to false

• @jdrogin why have you taken result == false in first statement of depth

• This post is deleted!

• @abhinav_smart
I guess here -1 is a boolean marker, since the types of return value of two functions are different.

• @mingyuan It seems be AVL tree algorithm. Here is my code which runs more time, because it caculates repeatedly.

``````class Solution {
public boolean isBalanced(TreeNode root) {
if(root == null) return true;
if(root.left == null && root.right == null) return true;
return Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
public int maxDepth(TreeNode node){
if(node == null) return 0;
return 1 + Math.max(maxDepth(node.left), maxDepth(node.right));
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.