Сума чисел на дереві

Дано масив цілих чисел. Побудуйте з нього Бінарне Дерево Пошуку. Якщо вставлюване значення дорівнює значенню поточної вершини, вставляйте його в праве піддерево.

Реалізуйте метод Sum, який обчислює суму чисел у всіх вершинах дерева.

Напишіть код відповідно до наступного інтерфейсу:

class TreeNode
{
public:
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Tree
{
public:
  TreeNode *head;
  Tree() : head(NULL) {};
  void Insert(int val); // Вставка числа val в Бінарне Дерево Пошуку
  int Sum(void); // Повернути суму чисел у всіх вершинах дерева
};

Ви можете створювати та використовувати додаткові методи за потреби.

Вхідні дані

Перший рядок містить число n (1 ≤ n ≤ 100). Другий рядок містить n цілих чисел.

Вихідні дані

Побудуйте Бінарне Дерево Пошуку з вхідних даних і виведіть суму чисел у всіх вершинах дерева.

Приклади