Как реализовать структуру бинарного дерева поиска в Scala

Прошу Вашей помощи друзья! Буду благодарен, если поможете.

Нужно реализовать структуру бинарного дерева поиска (элементы в левом поддереве меньше, чем элемент в корне, а элементы правого поддерева больше, чем элемент в корне). Для реализации:

1. Написать трейт Tree, определяющий абстрактные методы getLeftSubtree: Tree, getRightSubtree: Tree и getNodeData: Int.
2. Написать класс Node, который реализует трейт Tree и представляет собой узел дерева.
3. Написать класс Leaf, который реализует трейт Tree и представляет собой лист дерева.

Для реализованной структуры дерева написать следующие функции:

1. Функцию printTree(Tree): Unit, которая выводит на экран дерево
2. Функцию insert(Int, Tree): Tree, которая принимает элемент для вставки и корень дерева, возвращает корень нового дерева со вставленным элементом (при этом изначальное дерево изменяться не должно).
3. Функцию contains(Int, Tree): Boolean, которая возвращает true или false в зависимости от того, содержится ли заданное число в дереве, или нет.
4. Функцию sum(Tree): Int, которая возвращает сумму всех элементов в дереве.