Check if Binary tree is balanced or not

A quick interview exercise is to write code that checks whether a binary tree is balanced or not. Since a binary tree just begs for recursion, I decided to try it out in Scala. Takes less number of lines than I thought it would and it works. Logic works like this:

  1. If left node and right node are empty, tree is balanced
  2. If neither node is empty, just check that both left and right nodes are balanced
  3. If left node is empty, then right node can go down at most one more level
  4. If right node is empty, then left node can go down at most one more level

Here’s the code for it:

class Tree(val left: Tree, val right: Tree)

def isBalanced(tree: Tree): Boolean = {
  if (tree.left == null && tree.right == null)
    true
  else if (tree.left != null && tree.right != null) {
    isBalanced(tree.left) && isBalanced(tree.right)
  } else if (tree.left != null && tree.right == null) {
    tree.left.left == null && tree.left.right == null
  } else {
    tree.right.left == null && tree.right.right == null
  }

}   

 

Advertisements