Check Balanced

Implement a function to check if a binary tree is balanced. For the purposes of this question, a balanced tree is defined to be a tree such that the heights of the two subtress of any node never differ by more than one.

Solution

We can use a recursive algorithm to calculate the height of every node in the binary tree. If the recursive algorithm encounters a node which has children nodes which differ in height by more than 1, we can return an error value.

If the node has children, the algorithm will recurse on the children. If the node does not have children, the height of the children will be specified as 0. In this way, we can build a recursive algorithm which calculates the height of each node in the binary tree, and returns an error value if the height of the left child is more than 1 different than the height of the right child.

def check_height(node):
  if(node.left != None):
    left = check_height(node.left)
  else:
    left = 0

  if(left == -1):
    return -1

  if(node.right != None):
    right = check_height(node.right)
  else:
    right = 0

  if(right == -1):
    return -1

  diff = left - right

  if(abs(diff) > 1):
    return -1
  else:
    return max(left, right) + 1