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:
- If left node and right node are empty, tree is balanced
- If neither node is empty, just check that both left and right nodes are balanced
- If left node is empty, then right node can go down at most one more level
- 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
}}