CSc 4330/6330 Programming Language Concepts

Csc 4330/6330, Programming Language Concepts (Spring 2018)

Homework 5 (Due: 1 April (Sunday))

Binary Search Trees

In this Scala programming assignment, you will implement various set operations on Binary Search Tree implementations of Sets of integers. You will use "case classes" of Scala to represent a binary tree:

abstract class BT
case class Tree(left: BT, value: Int, right: BT) extends BT
object Nil extends BT

Using the above definitions, two examples of binary trees are shown below:

var t1 = Tree(Tree(Nil,10,Nil),20,Tree(Nil,30,Nil))
var t2 = Tree(Tree(Tree(Nil,10,Nil),20,Tree(Nil,30,Nil)),
              40,
              Tree(Tree(Nil,50,Nil),60,Tree(Nil,70,Nil)))

You will implement the following functions:

// returns true if t is a BST and false otherwise
def isBST(t: BT): Boolean = 

// returns the smallest element in BST t
def minBST(t: BT): Int = 

// returns the largest element in BST t
def maxBST(t: BT): Int = 

// returns true if x is a member of BST t, false otherwise
def memberBST(x: Int, t: BT): Boolean = 

// returns a new BST obtained by inserting x in BST t.
// should return t if x is already in t
def insertBST(x: Int, t: BT): BT = 

// returns a new BST obtained by deleting x in BST t.
// should return t if x is not in t
def deleteBST(x: Int, t: BT): BT = 

// returns the height of t; height is defined as the length of the
// longest path from root to leaf
def heightBST(t: BT): Int = 

// returns the number of elements in t
def sizeBST(t: BT): Int =

BST.scala
Driver.scala

You need to complete the function definitions in BST.scala.

Here is a run of the Driver program for my solution:

************************
Tree t3
tree(tree(tree(tree(nil,16,nil),20,nil),34,tree(nil,41,nil)),47,tree(tree(tree(nil,83,nil),88,nil),97,tree(tree(tree(nil,99,nil),100,nil),105,nil)))
( 16 20 34 41 47 83 88 97 99 100 105 )
************************
Tree t4
tree(tree(tree(nil,16,tree(nil,20,tree(tree(nil,34,nil),41,tree(nil,47,nil)))),83,tree(nil,88,nil)),97,tree(nil,99,tree(nil,100,tree(nil,105,nil))))
( 16 20 34 41 47 83 88 97 99 100 105 )
************************
isBST(t1)=true
isBST(t2)=false
minBST(t3)=16
maxBST(t3)=105
memberBST(44,t3)=false
memberBST(47,t3)=true

insertBST(24,t3)=tree(tree(tree(tree(nil,16,nil),20,tree(nil,24,nil)),34,tree(nil,41,nil)),47,tree(tree(tree(nil,83,nil),88,nil),97,tree(tree(tree(nil,99,nil),100,nil),105,nil)))
insertBST(24,t3) as a set=( 16 20 24 34 41 47 83 88 97 99 100 105 )


insertBST(101,t3)=tree(tree(tree(tree(nil,16,nil),20,nil),34,tree(nil,41,nil)),47,tree(tree(tree(nil,83,nil),88,nil),97,tree(tree(tree(nil,99,nil),100,tree(nil,101,nil)),105,nil)))
insertBST(101,t3) as a set=( 16 20 34 41 47 83 88 97 99 100 101 105 )


insertBST(97,t3)=tree(tree(tree(tree(nil,16,nil),20,nil),34,tree(nil,41,nil)),47,tree(tree(tree(nil,83,nil),88,nil),97,tree(tree(tree(nil,99,nil),100,nil),105,nil)))
insertBST(97,t3) as a set=( 16 20 34 41 47 83 88 97 99 100 105 )


insertBST(900,Nil)=tree(nil,900,nil)
insertBST(900,Nil) as a set=( 900 )


deleteBST(83,t3)=tree(tree(tree(tree(nil,16,nil),20,nil),34,tree(nil,41,nil)),47,tree(tree(nil,88,nil),97,tree(tree(tree(nil,99,nil),100,nil),105,nil)))
deleteBST(83,t3) as a set=( 16 20 34 41 47 88 97 99 100 105 )


deleteBST(105,t3)=tree(tree(tree(tree(nil,16,nil),20,nil),34,tree(nil,41,nil)),47,tree(tree(tree(nil,83,nil),88,nil),97,tree(tree(nil,99,nil),100,nil)))
deleteBST(105,t3) as a set=( 16 20 34 41 47 83 88 97 99 100 )


deleteBST(97,t3)=tree(tree(tree(tree(nil,16,nil),20,nil),34,tree(nil,41,nil)),47,tree(tree(tree(nil,83,nil),88,nil),99,tree(tree(nil,100,nil),105,nil)))
deleteBST(97,t3) as a set=( 16 20 34 41 47 83 88 99 100 105 )


deleteBST(22,t3)=tree(tree(tree(tree(nil,16,nil),20,nil),34,tree(nil,41,nil)),47,tree(tree(tree(nil,83,nil),88,nil),97,tree(tree(tree(nil,99,nil),100,nil),105,nil)))
deleteBST(22,t3) as a set=( 16 20 34 41 47 83 88 97 99 100 105 )

height of t3=5
height of t4=4
size of t3=11