Given a binary tree, find if it is height balanced or not. 
A tree is height balanced if difference between heights of left and right subtrees is not more than one for all nodes of tree. 
A height balanced tree
        1
     /     \
   10      39
  /
5
An unbalanced tree
        1
     /    
   10   
  /
5
Example 1:
Input:
      1
    /
   2
    \
     3 
Output: 0
Explanation: The max difference in height
of left subtree and right subtree is 2,
which is greater than 1. Hence unbalanced
Example 2:
Input:
       10
     /   \
    20   30 
  /   \
 40   60
Output: 1
Explanation: The max difference in height
of left subtree and right subtree is 1.
Hence balanced. 
Your Task:
You don't need to take input. Just complete the function isBalanced() that takes root node as parameter and returns true, if the tree is balanced else returns false.
Constraints:
1 <= Number of nodes <= 10^{5}
0 <= Data of a node <= 10^{6}
Expected time complexity: O(N)
Expected auxiliary space: O(h) , where h = height of tree

Source: geeksforgeeks | Difficulty: EASY
Tags: Tree algorithms

Data structures

Starter code: #User function Template for python3


'''class Node: 
    # Constructor to create a new Node 
    def __init__(self, data): 
        self.data = data 
        self.left = None
        self.right = None'''


#Function to check whether a binary tree is balanced or not.
class Solution:
    def isBalanced(self,root):
    
        #add code here



Solutions:
class Solution:

	def isBalanced(self, root):
		if root == None:
			return 1
		lh = self.isBalanced(root.left)
		if lh == 0:
			return 0
		rh = self.isBalanced(root.right)
		if rh == 0:
			return 0
		if abs(lh - rh) > 1:
			return 0
		return max(lh, rh) + 1


class Solution:

	def isBalanced(self, root):
		return self.Height(root) >= 0

	def Height(self, root):
		if root is None:
			return 0
		(leftheight, rightheight) = (self.Height(root.left), self.Height(root.right))
		if leftheight < 0 or rightheight < 0 or abs(leftheight - rightheight) > 1:
			return -1
		return max(leftheight, rightheight) + 1


class Solution:

	def nofn(self, root):
		if root is None:
			return 0
		l = self.nofn(root.left)
		r = self.nofn(root.right)
		if abs(l - r) > 1 or l == -1 or r == -1:
			return -1
		return 1 + max(l, r)

	def isBalanced(self, root):
		if self.nofn(root) == -1:
			return False
		else:
			return True


class Solution:

	def solve(self, root):
		if root == None:
			return 0
		left = self.solve(root.left)
		right = self.solve(root.right)
		if abs(left - right) > 1:
			return -1
		if left == -1 or right == -1:
			return -1
		return 1 + max(left, right)

	def isBalanced(self, root):
		if self.solve(root) == -1:
			return False
		else:
			return True


class Node:

	def __init__(self, data):
		self.data = data
		self.left = None
		self.right = None

class Solution:

	def isBalanced(self, root):
		return self.checkHeight(root) != -1

	def checkHeight(self, node):
		if node is None:
			return 0
		left_height = self.checkHeight(node.left)
		if left_height == -1:
			return -1
		right_height = self.checkHeight(node.right)
		if right_height == -1:
			return -1
		if abs(left_height - right_height) > 1:
			return -1
		return max(left_height, right_height) + 1


class Solution:

	def isBalanced(self, root):

		def solve(root):
			if not root:
				return 0
			l = solve(root.left)
			r = solve(root.right)
			if abs(l - r) > 1:
				return -1
			if l == -1 or r == -1:
				return -1
			return 1 + max(l, r)
		if solve(root) == -1:
			return False
		return True


class Solution:

	def isBalanced(self, root):
		return height(root) != -1

def height(root):
	if root == None:
		return 0
	l = height(root.left)
	r = height(root.right)
	if abs(l - r) > 1:
		return -1
	if l == -1 or r == -1:
		return -1
	return max(l, r) + 1


class Solution:

	def isBalanced(self, root):
		f = []
		Solution.Balanced(self, root, f)
		if len(f) == 0:
			return True
		return False

	def Balanced(self, root, f):
		if root == None:
			return 0
		x = Solution.Balanced(self, root.left, f)
		y = Solution.Balanced(self, root.right, f)
		if abs(x - y) > 1:
			f.append(0)
		return max(x, y) + 1


class Solution:

	def isBalanced(self, root):
		self.ans = True

		def dfs(x, h):
			if not x:
				return h - 1
			left = dfs(x.left, h + 1)
			right = dfs(x.right, h + 1)
			if abs(right - left) > 1:
				self.ans = False
			return max(left, right)
		dfs(root, 0)
		return self.ans


class Solution:

	def isBalanced(self, root):

		def IsBalance(root):
			if root == None:
				return 0
			l = IsBalance(root.left)
			r = IsBalance(root.right)
			if abs(l - r) > 1:
				return float('inf')
			return max(l, r) + 1
		if IsBalance(root) < float('inf'):
			return True
		return False


class Solution:

	def isBalanced(self, root):
		res = [True]

		def findBalanced(root, res):
			if root == None:
				return 0
			if root.left == None and root.right == None:
				return 1
			l = findBalanced(root.left, res)
			r = findBalanced(root.right, res)
			if abs(l - r) > 1:
				res[0] = False
			return max(l, r) + 1
		findBalanced(root, res)
		return res[0]


class Solution:

	def height(self, root):
		if root == None:
			return 0
		lh = self.height(root.left)
		rh = self.height(root.right)
		if abs(lh - rh) > 1:
			return -1
		if lh == -1 or rh == -1:
			return -1
		return max(lh, rh) + 1

	def isBalanced(self, root):
		if self.height(root) == -1:
			return False
		else:
			return True


class Solution:

	def isBalanced(self, root):

		def dfs(root):
			if root is None:
				return [True, 0]
			(left, right) = (dfs(root.left), dfs(root.right))
			balanced = left[0] and right[0] and (abs(left[1] - right[1]) <= 1)
			return [balanced, 1 + max(left[1], right[1])]
		return dfs(root)[0]


class Solution:

	def balnced(self, A, blnced):
		if A == None:
			return 0
		l = self.balnced(A.left, blnced)
		r = self.balnced(A.right, blnced)
		z = abs(r - l)
		if z > 1:
			blnced[0] = 0
		return max(l, r) + 1

	def isBalanced(self, root):
		blnced = [0] * 1
		blnced[0] = 1
		self.balnced(root, blnced)
		return blnced[0]


class Solution:

	def height(self, root):
		if not root:
			return 0
		lh = Solution.height(self, root.left)
		if lh == -1:
			return -1
		rh = Solution.height(self, root.right)
		if rh == -1:
			return -1
		if abs(lh - rh) > 1:
			return -1
		return 1 + max(lh, rh)

	def isBalanced(self, root):
		return Solution.height(self, root) != -1


class Solution:

	def isBalanced(self, root):

		def checkbalance(root):
			if root is None:
				return 0
			left_height = checkbalance(root.left)
			if left_height == -1:
				return -1
			right_height = checkbalance(root.right)
			if right_height == -1:
				return -1
			if abs(left_height - right_height) > 1:
				return -1
			return 1 + max(left_height, right_height)
		result = checkbalance(root)
		return result != -1


class Solution:

	def isBalanced(self, root):

		def checkbalance(root):
			if root is None:
				return (True, 0)
			(left_bal, left_height) = checkbalance(root.left)
			if not left_bal:
				return (False, 0)
			(right_bal, right_height) = checkbalance(root.right)
			if not right_bal:
				return (False, 0)
			if abs(left_height - right_height) <= 1:
				return (True, 1 + max(left_height, right_height))
			return (False, 0)
		result = checkbalance(root)
		return result[0]


class Solution:

	def bal(self, root):
		if not root:
			return (True, 0)
		(leftbool, hleft) = self.bal(root.left)
		(rightbool, hright) = self.bal(root.right)
		diff = abs(hleft - hright)
		if leftbool and rightbool and (diff <= 1):
			return (True, max(hleft, hright) + 1)
		return (False, 0)

	def isBalanced(self, root):
		if not root:
			return True
		return self.bal(root)[0]


class Solution:
	Flag = True

	def solve(self, root):
		if root == None:
			return 0
		l = self.solve(root.left)
		r = self.solve(root.right)
		if abs(l - r) > 1:
			self.Flag = False
		return max(l, r) + 1

	def isBalanced(self, root):
		self.solve(root)
		return self.Flag


class Solution:

	def is_balanced_fast(self, root):
		if root is None:
			return (True, 0)
		left = self.is_balanced_fast(root.left)
		right = self.is_balanced_fast(root.right)
		is_left = left[0]
		is_right = right[0]
		is_balanced = abs(left[1] - right[1]) <= 1
		height = max(left[1], right[1]) + 1
		if is_left and is_right and is_balanced:
			return (True, height)
		return (False, height)

	def isBalanced(self, root) -> bool:
		res = self.is_balanced_fast(root)
		return res[0]


class Solution:

	def height(self, node):
		if not node:
			return 0
		leftHeight = self.height(node.left)
		if leftHeight == -1:
			return -1
		rightHeight = self.height(node.right)
		if rightHeight == -1:
			return -1
		if abs(leftHeight - rightHeight) > 1:
			return -1
		return max(leftHeight, rightHeight) + 1

	def isBalanced(self, root):
		return self.height(root) != -1


class Solution:
	flag = 1

	def solve(self, root):
		if root == None:
			return 0
		left = self.solve(root.left)
		right = self.solve(root.right)
		if abs(left - right) > 1:
			self.flag = 0
		return max(left, right) + 1

	def isBalanced(self, root):
		self.solve(root)
		return self.flag


class Solution:

	def isBalanced(self, root):
		is_balanced = True

		def height(root):
			nonlocal is_balanced
			if root is None:
				return 0
			left = height(root.left)
			right = height(root.right)
			if abs(left - right) > 1:
				is_balanced = False
			ans = max(left, right) + 1
			return ans
		height(root)
		return is_balanced


class Solution:

	def isBalanced(self, root):
		ans = self.solve(root)
		if ans == -1:
			return 0
		return 1

	def solve(self, root):
		if root is None:
			return 0
		l = self.solve(root.left)
		if l == -1:
			return -1
		r = self.solve(root.right)
		if r == -1:
			return -1
		if abs(l - r) > 1:
			return -1
		else:
			return max(l, r) + 1


class Solution:

	def isBalanced(self, root):

		def height(root):
			if not root:
				return 0
			left_height = height(root.left)
			if left_height == -1:
				return -1
			right_height = height(root.right)
			if right_height == -1 or abs(left_height - right_height) > 1:
				return -1
			return max(left_height, right_height) + 1
		return height(root) != -1


class Solution:

	def height(self, root, cache):
		if root is None:
			return 0
		if root in cache:
			return cache[root]
		left_height = self.height(root.left, cache)
		right_height = self.height(root.right, cache)
		height = max(left_height, right_height) + 1
		cache[root] = height
		return height

	def isBalanced(self, root):
		cache = {}

		def dfs(node):
			if node is None:
				return True
			left_height = self.height(node.left, cache)
			right_height = self.height(node.right, cache)
			if abs(left_height - right_height) > 1:
				return False
			return dfs(node.left) and dfs(node.right)
		return dfs(root)


class Height:

	def __init__(self):
		self.height = 0

def isBalancedUtil(root, height):
	lh = Height()
	rh = Height()
	if root is None:
		return True
	l = isBalancedUtil(root.left, lh)
	r = isBalancedUtil(root.right, rh)
	height.height = max(lh.height, rh.height) + 1
	if abs(lh.height - rh.height) >= 2:
		return False
	else:
		return l and r

class Solution:

	def isBalanced(self, root):
		height = Height()
		return isBalancedUtil(root, height)


class Solution:

	def isBalanced(self, root):
		(height, balanced) = self.isBalancedHelper(root)
		return balanced

	def isBalancedHelper(self, root):
		if root is None:
			return (0, True)
		(lh, isLeftBalanced) = self.isBalancedHelper(root.left)
		(rh, isRightBalanced) = self.isBalancedHelper(root.right)
		h = 1 + max(lh, rh)
		if abs(lh - rh) > 1:
			return (h, False)
		if isLeftBalanced and isRightBalanced:
			return (h, True)
		else:
			return (h, False)


class Solution:

	def height(self, node):
		if not node:
			return 0
		left = self.height(node.left)
		right = self.height(node.right)
		bf = abs(left - right)
		if bf > 1 or left == -1 or right == -1:
			return -1
		return max(left, right) + 1

	def isBalanced(self, root):
		if not root:
			return 0
		return 0 if self.height(root) == -1 else self.height(root)


class Solution:

	def isBalanced(self, root):
		isBalance = [True]

		def height(root, isBalance):
			if root is None:
				return 0
			lh = 1 + height(root.left, isBalance)
			rh = 1 + height(root.right, isBalance)
			if abs(lh - rh) > 1:
				isBalance[0] = False
			return max(lh, rh)
		height(root, isBalance)
		return isBalance[0]


class Solution:

	def isBalancedfast(self, root):
		if root is None:
			return (True, 0)
		left = self.isBalancedfast(root.left)
		right = self.isBalancedfast(root.right)
		leftAns = left[0]
		rightAns = right[0]
		diff = abs(left[1] - right[1]) <= 1
		height = max(left[1], right[1]) + 1
		if leftAns and rightAns and diff:
			return (True, height)
		else:
			return (False, height)

	def isBalanced(self, root):
		return self.isBalancedfast(root)[0]


def func(root):
	if root is None:
		return 0
	l = func(root.left)
	r = func(root.right)
	if l == -1 or r == -1 or abs(l - r) > 1:
		return -1
	return max(l, r) + 1

class Solution:

	def isBalanced(self, root):
		ans = []
		if root is None:
			return
		lt = func(root)
		return lt != -1


class Solution:

	def test(self, root):
		if root is None:
			return 0
		l = self.test(root.left)
		r = self.test(root.right)
		if l == -1 or r == -1:
			return -1
		if abs(l - r) > 1:
			return -1
		return 1 + max(l, r)

	def isBalanced(self, root):
		h = self.test(root)
		if h == -1:
			return False
		return True


class Solution:

	def __init__(self):
		self.dp = {}

	def isBalanced(self, root):
		if not root:
			return True
		return abs(self.heightOfTree(root.left) - self.heightOfTree(root.right)) < 2 and self.isBalanced(root.left) and self.isBalanced(root.right)

	def heightOfTree(self, root):
		if not root:
			self.dp[root] = 0
			return 0
		elif root in self.dp:
			return self.dp[root]
		else:
			self.dp[root] = 1 + max(self.heightOfTree(root.left), self.heightOfTree(root.right))
			return self.dp[root]


class Solution:

	def isBalanced(self, root):
		COUNT = [10]

		def print2DUtil(root, space):
			if root == None:
				return
			space += COUNT[0]
			print2DUtil(root.right, space)
			print()
			for i in range(COUNT[0], space):
				print(end=' ')
			print(root.data)
			print2DUtil(root.left, space)

		def print2D(root):
			print2DUtil(root, 0)

		def find_max_hight(root):
			max_hight = 0
			if not root:
				return 0
			if root:
				max_hight = max(max_hight, find_max_hight(root.left) + 1)
				max_hight = max(max_hight, find_max_hight(root.right) + 1)
			return max_hight

		def isBalncedUtil(root):
			if not root:
				return 0
			left_hight = isBalncedUtil(root.left)
			if left_hight == -1:
				return -1
			right_hight = isBalncedUtil(root.right)
			if right_hight == -1:
				return -1
			if abs(left_hight - right_hight) > 1:
				return -1
			else:
				return max(left_hight, right_hight) + 1
		return False if isBalncedUtil(root) == -1 else True


class Solution:
	result = 1

	def isBalanced(self, root):
		self.Height(root)
		return self.result

	def Height(self, root):
		if root == None:
			return 0
		left = self.Height(root.left)
		right = self.Height(root.right)
		if abs(left - right) > 1:
			self.result = 0
		return max(left, right) + 1


class Solution:

	def height(self, node):
		if node is None:
			return 0
		return max(self.height(node.left), self.height(node.right)) + 1

	def isBalanced(self, root):
		if self.isBalanced_optimized(root) == -1:
			return False
		else:
			return True

	def isBalanced_optimized(self, root):
		if root is None:
			return 0
		lh = self.isBalanced_optimized(root.left)
		if lh == -1:
			return -1
		rh = self.isBalanced_optimized(root.right)
		if rh == -1:
			return -1
		if abs(lh - rh) > 1:
			return -1
		else:
			return max(lh, rh) + 1


class Solution:

	def isBalanced(self, root):
		return self.getHeight(root) >= 0

	def getHeight(self, root):
		if root == None:
			return 0
		left_height = self.getHeight(root.left)
		right_height = self.getHeight(root.right)
		if left_height < 0 or right_height < 0 or abs(left_height - right_height) > 1:
			return -1
		return max(left_height, right_height) + 1


class Solution:

	def isBalanced(self, root):

		def fun(root):
			if root is None:
				return 0
			lh = fun(root.left)
			rh = fun(root.right)
			if lh == -1 or rh == -1:
				return -1
			if abs(lh - rh) > 1:
				return -1
			return max(lh, rh) + 1
		if fun(root) == -1:
			return False
		return True


class Solution:

	def isBalanced(self, root):

		def dfs(root):
			if not root:
				return 0
			(left, right) = (dfs(root.left), dfs(root.right))
			if left == -1:
				return -1
			if right == -1:
				return -1
			if abs(left - right) > 1:
				return -1
			return max(left, right) + 1
		return dfs(root) != -1


class Solution:

	def isBalanced(self, root):
		answer = True

		def dfs(root):
			if not root:
				return 1
			left = dfs(root.left)
			right = dfs(root.right)
			if abs(left - right) > 1:
				nonlocal answer
				answer = False
			return 1 + max(left, right)
		dfs(root)
		return answer


class Solution:

	def depth(self, node):
		if node is None:
			return (True, 0)
		(lb, l) = self.depth(node.left)
		(rb, r) = self.depth(node.right)
		if not lb or not rb:
			return (False, -1)
		if l - r <= 1 and r - l <= 1:
			return (True, max(r, l) + 1)
		return (False, -1)

	def isBalanced(self, root):
		return self.depth(root)[0]


class Solution:

	def isBalanced(self, root):

		def height(root):
			if root is None:
				return 0
			left_height = height(root.left)
			if left_height == -1:
				return -1
			right_height = height(root.right)
			if right_height == -1:
				return -1
			d = abs(left_height - right_height)
			if d > 1:
				return -1
			return 1 + max(left_height, right_height)
		h = height(root)
		if h == -1:
			return 0
		return 1


class Solution:

	def isBalanced(self, root):

		def Height(root):
			if root is None:
				return 0
			leftHeight = Height(root.left)
			if leftHeight == -1:
				return -1
			rightHeight = Height(root.right)
			if rightHeight == -1:
				return -1
			if abs(leftHeight - rightHeight) > 1:
				return -1
			return max(leftHeight, rightHeight) + 1
		if Height(root) == -1:
			return 0
		return 1


class Solution:

	def isBalanced(self, root):

		def checkBalanced(root):
			if root is None:
				return 0
			lh = checkBalanced(root.left)
			rh = checkBalanced(root.right)
			if lh == -1 or rh == -1:
				return -1
			if abs(lh - rh) > 1:
				return -1
			else:
				return 1 + max(lh, rh)
		x = checkBalanced(root)
		if x == -1:
			return 0
		else:
			return 1


class Solution:

	def isBalanced(self, root):
		if root is None:
			return 1
		left = self.isBalanced(root.left)
		right = self.isBalanced(root.right)
		if abs(left - right) > 1:
			return 0
		if left == 0 or right == 0:
			return 0
		return 1 + max(left, right)
		if self.isbalanced(root) == -1:
			return False
		return True


class Solution:

	def isBalanced(self, root):

		def heightBalanced(root):
			if root == None:
				return (0, True)
			(l, lb) = heightBalanced(root.left)
			(r, rb) = heightBalanced(root.right)
			(l, r) = (l + 1, r + 1)
			return (max(l, r), abs(l - r) <= 1 and lb and rb)
		(l, b) = heightBalanced(root)
		return b


class Solution:

	def isBalanced(self, root):

		def checkIsBalanced(root):
			if root == None:
				return (0, True)
			(lh, isLeft) = checkIsBalanced(root.left)
			(rh, isRight) = checkIsBalanced(root.right)
			h = 1 + max(lh, rh)
			if abs(lh - rh) > 1:
				return (h, False)
			if isLeft and isRight:
				return (h, True)
			else:
				return (h, False)

		def output(root):
			(ht, isBalanced) = checkIsBalanced(root)
			return isBalanced
		return output(root)


class Solution:

	def isBalanced(self, root):

		def check(root):
			if root == None:
				return (0, True)
			(lh, isLeftBal) = check(root.left)
			(rh, isRightBal) = check(root.right)
			h = 1 + max(lh, rh)
			if lh - rh > 1 or rh - lh > 1:
				return (h, False)
			if isLeftBal and isRightBal:
				return (h, True)
			else:
				return (h, False)
		(h, ans) = check(root)
		if ans:
			return 1
		return 0


class Solution:

	def balanced_final(self, root):
		if root is None:
			return {'balanced': True, 'height': 0}
		left = self.balanced_final(root.left)
		right = self.balanced_final(root.right)
		diff = abs(left['height'] - right['height']) <= 1
		return {'balanced': left['balanced'] and right['balanced'] and diff, 'height': max(left['height'], right['height']) + 1}

	def isBalanced(self, root):
		val = self.balanced_final(root)
		return val['balanced']


from collections import namedtuple

class Solution:

	def isBalanced(self, root):
		status = namedtuple('status', ('balanced', 'height'))

		def balanced_check(tree):
			if not tree:
				return status(True, -1)
			left_subtree = balanced_check(tree.left)
			if not left_subtree.balanced:
				return status(False, 0)
			right_subtree = balanced_check(tree.right)
			if not right_subtree.balanced:
				return status(False, 0)
			balanced = abs(left_subtree.height - right_subtree.height) <= 1
			height = max(left_subtree.height, right_subtree.height) + 1
			return status(balanced, height)
		return balanced_check(root).balanced


class Solution:

	def isBalanced(self, root):

		def is_balanced(root):
			if root is None:
				return (True, 0)
			(is_balanced_l, height_l) = is_balanced(root.left)
			(is_balanced_r, height_r) = is_balanced(root.right)
			balanced = is_balanced_l and is_balanced_r and (abs(height_l - height_r) <= 1)
			height = 1 + max(height_l, height_r)
			return (balanced, height)
		(b, _) = is_balanced(root)
		return b


def height(root):
	if not root:
		return (0, True)
	(lh, bl) = height(root.left)
	(rh, br) = height(root.right)
	height_of_tree = max(lh, rh) + 1
	if abs(lh - rh) <= 1 and br and bl:
		return (height_of_tree, True)
	else:
		return (height_of_tree, False)

class Solution:

	def isBalanced(self, root):
		(h, bool) = height(root)
		if bool:
			return 1
		else:
			return 0


def height(root):
	if root is None:
		return (0, True)
	(leftheight, bl) = height(root.left)
	(rightheight, br) = height(root.right)
	height_of_tree = 1 + max(leftheight, rightheight)
	if abs(leftheight - rightheight) <= 1 and bl and br:
		return (height_of_tree, True)
	else:
		return (height_of_tree, False)

class Solution:

	def isBalanced(self, root):
		(height_of_tree, bool) = height(root)
		if bool:
			return 1
		return 0


def bal(root):
	if root is None:
		return (0, True)
	(lh, bl) = bal(root.left)
	(rh, br) = bal(root.right)
	height = 1 + max(lh, rh)
	if abs(lh - rh) <= 1 and bl and br:
		return (height, True)
	else:
		return (height, False)

class Solution:

	def isBalanced(self, root):
		(h, bool) = bal(root)
		if bool:
			return 1
		return 0


class Solution:

	def __init__(self):
		self.left = []
		self.right = []

	def height(self, root):
		if root == None:
			return 0
		l = self.height(root.left)
		r = self.height(root.right)
		self.left.append(l)
		self.right.append(r)
		return max(l, r) + 1

	def isBalanced(self, root):
		self.height(root)
		for i in range(len(self.left)):
			if abs(self.left[i] - self.right[i]) > 1:
				return False
		return True


class Solution:

	def solve(self, root):
		if root is None:
			return 1
		lh = self.solve(root.left)
		rh = self.solve(root.right)
		if lh == False:
			return False
		if rh == False:
			return False
		if abs(lh - rh) > 1:
			return False
		else:
			return max(lh, rh) + 1

	def isBalanced(self, root):
		return self.solve(root)


class Solution:

	def height(self, root):
		if root == None:
			return 0
		ls = self.height(root.left)
		rs = self.height(root.right)
		if abs(ls - rs) > 1:
			return -1
		if ls == -1 or rs == -1:
			return -1
		return 1 + max(ls, rs)

	def isBalanced(self, root):
		if self.height(root) == -1:
			return False
		return True