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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s