eolymp
bolt
Try our new interface for solving problems
Problems

Sum of numbers in a tree

Sum of numbers in a tree

Time limit 1 second
Memory limit 122 MiB

Given an array of integers. Create a Binary Search Tree from these numbers. If the inserted value equals to the current node, insert it to the right subtree.

Write method Sum that returns the sum of numbers in all nodes of a tree.

prb7463.gif

Write the code according to the next interface:

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); // Insert number val to Binary Search Tree

int Sum(void); // Return the sum of numbers in all nodes of a tree

};

You can create (use) additional methods if needed.

Input data

The first line contains number n (1n100). The second line contains n integers.

Output data

Create the Binary Search Tree from input data. Print the sum of numbers in all nodes of a tree.

Examples

Input example #1
6
14 9 1 14 20 13
Output example #1
71
Author Mykhailo Medvediev
Source С++