"""
https://www.youtube.com/watch?v=SH3qzLmLoS0 in chinese
"""


"""
You are given a binary tree and you need 
to write a function that can determine if it is height-balanced.

A height-balanced tree can be defined as a binary tree 
in which the left and right subtrees of every node differ in height by a maximum of 1.

Example 1:
Given the following tree [5,10,25,None,None,12,3]:

    5
   / \
 10  25
    /  \
   12   3
return True.

Example 2:
Given the following tree [5,6,6,7,7,None,None,8,8]:

       5
      / \
     6   6
    / \
   7   7
  / \
 8   8
return False.
"""

#
# Binary trees are already defined with this interface:
class Tree(object):
  def __init__(self, x):
    self.value = x
    self.left = None
    self.right = None

def balancedBinaryTree(root):

    def get_height(root):

        # Case at Root
        if root is None:
            return 0

        # we traverse down the left and right sides
        left_height = get_height(root.left)
        right_height = get_height(root.right)
        
        # the tree is not balanced, one side is longer than the other
        if left_height < 0 or right_height < 0 or abs(left_height - right_height) > 1:
            return -1

        # the tree is balanced
        return max(left_height, right_height) + 1

    return (get_height(root) >= 0)

"""
https://www.youtube.com/watch?v=SH3qzLmLoS0 in chinese
"""


"""
You are given a binary tree and you need 
to write a function that can determine if it is height-balanced.

A height-balanced tree can be defined as a binary tree 
in which the left and right subtrees of every node differ in height by a maximum of 1.

Example 1:
Given the following tree [5,10,25,None,None,12,3]:

    5
   / \
 10  25
    /  \
   12   3
return True.

Example 2:
Given the following tree [5,6,6,7,7,None,None,8,8]:

       5
      / \
     6   6
    / \
   7   7
  / \
 8   8
return False.
"""

#
# Binary trees are already defined with this interface:
class Tree(object):
  def __init__(self, x):
    self.value = x
    self.left = None
    self.right = None

def balancedBinaryTree(root):

    def get_height(root):

        # Case at Root
        if root is None:
            return 0

        # we traverse down the left and right sides
        left_height = get_height(root.left)
        right_height = get_height(root.right)
        
        # the tree is not balanced, one side is longer than the other
        if left_height < 0 or right_height < 0 or abs(left_height - right_height) > 1:
            return -1

        # the tree is balanced
        return max(left_height, right_height) + 1

    return (get_height(root) >= 0)

https://www.youtube.com/watch?v=SH3qzLmLoS0 in chinese You are given a binary tree and you need  to write a function that can determine if it is height-balanced.  A height-balanced tree can be defined as a binary tree  in which the left and right subtrees of every node differ in height by a maximum of 1.  Example 1: Given the following tree [5,10,25,None,None,12,3]:      5    / \  10  25     /  \    12   3 return True.  Example 2: Given the following tree [5,6,6,7,7,None,None,8,8]:         5       / \      6   6     / \    7   7   / \  8   8 return False. # # Binary trees are already defined with this interface: # Case at Root # we traverse down the left and right sides # the tree is not balanced, one side is longer than the other # the tree is balanced