Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Question by Osman Ay.
Sum of the Leaves
A binary search tree (BST), also called ordered binary tree,
is a type of binary tree where the nodes are arranged in order:
for each node, all elements in its left subtree are less than the
node (<), and all the elements in its right subtree are greater
than the node (>). BST has the following properties:
- Each node has a unique value.
- A total order is defined on these values.
- The left subtree of a node contains only values less than the node's value.
- The right subtree of a node contains only values greater than the node's value.
The tree in the picture is obtained by inserting the values
4, 2, 1, 3, 2, 4, 6, and 5 in that order, starting from an empty
tree. In the tree, the value of the root is 4, and the values of
leaves are 1, 3 and 5. Make a program that calculates the sum of
the leaf nodes' values of the binary search tree that is
constructed from a given list of positive integers.
Input specification
Input has two lines. The first line of the input contains an
integer N (1 ≤ N ≤ 10000) that represents the number
of the integers in the list. The second line contains a list
of N integers between 1 and 1000.
Output specification
Output contains a single integer that is the sum of
the values of the leaf nodes.
Sample Input I
8
4 2 1 3 2 4 6 5
|
Sample Input II
10
13 10 10 20 4 17 2 20 11 17
|
Sample Output I
9
|
Sample Output II
30
|
Для отправки решений необходимо выполнить вход.
|