Scala By Example Chapter 7 Solutions - Exercise 7.2.2

Exercise 7.2.2 Complete the following implementations of function contains and insert for IntTree’s.

This is similar to the IntSet implementations in Chapter 6.

	object IntTreeTest {
	abstract class IntTree
	case object EmptyTree extends IntTree
	case class Node(elem: Int, left: IntTree, right: IntTree) extends IntTree
	def contains(t: IntTree, v: Int): Boolean = t match {
	case EmptyTree => false
	case Node(e, l, r) =>
	if (v < e) contains(l, v)
	else if (v > e) contains(r, v)
	else true
	}
	def insert(t: IntTree, v: Int): IntTree = t match {
	case EmptyTree => Node(v, EmptyTree, EmptyTree)
	case Node(e, l, r) =>
	if (v < e) Node(e, insert(l, v), r)
	else if (v > e) Node(e, l, insert(r, v))
	else t
	}
	def main(args: Array[String]) {
	val t = insert(insert(insert(insert(insert(EmptyTree, 11), 1), 20), 18), 25)
	println("Tree is: " + t)
	println("Does Tree contain 20?: " + (if (contains(t, 20)) "Yes" else "No"))
	println("Does Tree contain 15?: " + (if (contains(t, 15)) "Yes" else "No"))
	}
	}

view raw IntTreeTest.scala hosted with ❤ by GitHub