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 )