Balanced Binary Tree

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

import scala.collection.mutable

trait BTree

object Empty extends BTree

case class Node(var value: Int, var left: BTree = Empty, var right: BTree = Empty) extends BTree

def printBTree(root: BTree): Unit = {
  val queue = mutable.Queue[(BTree, Int)]((root, 0))
  var prev = -1
  while (!queue.isEmpty) {
    val (node, level) = queue.dequeue()
    node match {
      case n: Node => {
        if (level != prev) {
          print("\n#")
          prev = level
        }
        print(n.value)
        queue.enqueue((n.left, level + 1))
        queue.enqueue((n.right, level + 1))
      }
      case _ =>
    }
  }
}

/**
  * 4.1
  *
  * @param root
  * @return
  */
def isBalanced(root: BTree): Boolean = {
  def depth(node: BTree): Int = {
    node match {
      case Empty => 0
      case n: Node => {
        val (left, right) = (depth(n.left), depth(n.right))
        if (left == -1 || right == -1 || math.abs(left - right) > 1) -1
        else (left max right) + 1
      }
    }
  }
  depth(root) != -1
}

val a = Node(1, Empty, Empty)
val b = Node(2, Empty, Empty)
val c = Node(3, a, b)

isBalanced(Empty)
isBalanced(c)

val e = Node(4, Empty, a)
val d = Node(5, Empty, e)
val f = Node(5, Empty, d)

isBalanced(f)

Last updated