Scala language

You must provide a signature for every function, including the return type. Whenever meaningful, use type variables instead of types. Finally, ensure that the parameters passed to the functions are of the correct types and are passed in the correct order.

Problem

Define a polymorphic Tree data type, where a Tree is either a Node with a left subtree, a value, and a right subtree; or it is a Leaf with just a value. [11 Points]

Also define a companion object for the Tree data type, with the following functions:

(a) 6 Three polymorphic functions -- inOrder, preOrder, and postOrder -- to traverse the tree in-order, pre-order, and post-order. Each function takes a tree and returns a list with the contents of the tree when traversed in that order.

(b) A polymorphic function, search, which takes two arguments a Tree and a key and returns a boolean result based on whether the key is found in the tree.

(c) A polymorphic function, replace, which takes three arguments a Tree t, a value before, and a value after and returns a variant of t with ALL instances of before replaced with the value after.