SCALA!!!

class TreeDemo[T](implicit o : T => Ordered[T]) { sealed trait BinaryTree case object Empty extends BinaryTree case class Node(left:BinaryTree, d:T, right:BinaryTree) extends BinaryTree

def Leaf(d : T) : BinaryTree = Node(Empty,d,Empty)

def traverse(t : BinaryTree) : List[T] = t match { case Empty => Nil case Node(l, d, r) => traverse(l) ++ List(d) ++ traverse(r) }

// remove all nodes equal to x from tree t def remove(t : BinaryTree, x : T) : BinaryTree = { replace(t, x, Empty) }

// TODO: replace all nodes equal to x in tree t with subtree s def replace(t : BinaryTree, x : T, s : BinaryTree) : BinaryTree = { t match { case Empty => Empty case Node(l, d, r) => { // TODO Empty } } }

// TODO: check if t is a binary search tree def isBST(t : BinaryTree) : Boolean = { t match { case Empty => true case Node(l, d, r) => { // TODO false } } }

// TODO: insert element x into binary search tree t def insertBST(t : BinaryTree, x : T) : BinaryTree = { t match { case Empty => Leaf(x) case Node(l,d,r) => { // TODO Empty } } }

}

TEST OUTPUTS:

import org.scalatest.FlatSpec

// unit tests for the Tree functions class TreeDemoTest extends FlatSpec { val td = new TreeDemo[Int] import td._

val myTree = Node(Node(Leaf(1),2,Leaf(3)),4,Leaf(5))

"Remove" should "properly remove the left subtree in the integer example" in { assert(td.remove(myTree, 2) === Node(Empty,4,Leaf(5))) }

"Replace" should "properly replace the left subtree in the integer example" in { assert(td.replace(myTree, 2, myTree) === Node(myTree,4,Leaf(5))) }

"Is BST" should "give the correct answer for integer example" in { assert(td.isBST(myTree) === true) }

"BST Insert" should "give the correct answer for integer example" in { assert(td.insertBST(myTree,6) === td.replace(myTree,5,Node(Empty,5,Leaf(6)))) }