Validates a Binary Search Tree

validatetree.scala

// Validates a binary search tree (BST) to make sure 
// all nodes are in order.  
//
// Same implementation as https://gist.github.com/hectorcorrea/9064942 in JavaScript

class Node(theValue: Int, leftNode: Node, rightNode: Node) {
  def value = theValue
  def left = leftNode
  def right = rightNode
  override def toString = value.toString
}


class Tree(theRoot: Node) {
  def root = theRoot

  def Walk : String = WalkNode(root)


  def WalkNode(node: Node) : String = 
    if (node == null) 
      "."
    else 
      WalkNode(node.left) + node.value.toString + WalkNode(node.right)


  def IsValid : Boolean = {
    
    var lastValue = -1
    var isFirstNode = true
    def validator(value: Int) : Boolean = {
      
      if (isFirstNode) {
        lastValue = value
        isFirstNode = false
        true
      }
      else {

        if(value < lastValue) 
          false
        else {
          lastValue = value
          true
        }

      }
    }
    
    IsValid(root, validator)
  } 


  def IsValid(node: Node, validateNode: Int => Boolean) : Boolean = {
    if (node == null) true
    else IsValid(node.left, validateNode) && 
      validateNode(node.value) && 
      IsValid(node.right, validateNode)
  }


  override def toString = Walk
}


object ValidTree {

  def sample1() : Tree = {
    // valid: 5-10,15
    val l = new Node(5, null, null)
    val r = new Node(15, null, null)
    val root = new Node(10, l, r)
    new Tree(root)
  }

  def sample2() : Tree = {
    // invalid: 14-10-15
    val l = new Node(14, null, null)
    val r = new Node(15, null, null)
    val root = new Node(10, l, r)
    new Tree(root)
  }

  def sample3() : Tree = {
    // valid tree: 2-5-6-10-13-15-20
    val l = new Node(5, new Node(2, null, null), new Node(6, null, null))
    val r = new Node(15, new Node(13, null, null), new Node(20, null, null))
    val root = new Node(10, l, r)
    new Tree(root)
  }

  def sample4() : Tree = {
    // invalid tree: 2-54-6-10-13-15-20
    val l = new Node(54, new Node(2, null, null), new Node(6, null, null))
    val r = new Node(15, new Node(13, null, null), new Node(20, null, null))
    val root = new Node(10, l, r)
    new Tree(root)
  }

  def sample5() : Tree = {
    // invalid tree: 1-5-6-10-4-15-20
    val l = new Node(5, new Node(1, null, null), new Node(6, null, null))
    val r = new Node(15, new Node(4, null, null), new Node(20, null, null))
    val root = new Node(10, l, r)
    new Tree(root)
  }

  def main() {

    var trees = new Array[Tree](5)
    trees(0) = sample1()
    trees(1) = sample2()
    trees(2) = sample3()
    trees(3) = sample4()
    trees(4) = sample5()
    for(tree <- trees) {
      val valid = tree.IsValid
      println(s"T: $tree $valid")
    }

  }
}

ValidTree.main()