Feedback | | If you notice incorrect translations in Contester, please let author know.
|
|
Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Question by Sidrit Reka.
Sorting BST Nodes
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:
1. Each node has a unique value.
2. A total order is defined on these values.
3. The left subtree of a node contains only
values less than the node's value.
4. The right subtree of a node contains only
values greater than the node's value.
5. The depth of a node in a tree, is the
number of steps to reach to the node from
the root.
6. The depth of the root node is
assumed to be zero.
Question:
You will be given a series of numbers to
be inserted into an initially empty
Binary Search Tree (BST). Sort all the
nodes in ascending order according to
their depths in the BST. If two nodes
have the same depth, sort them in
descending order according to their
values.
Input specification
You will be first given a number (n) the
number of nodes to be inserted in the BST
where 1 <= n <= 10,000. Then, you will be
given n space separated numbers (nums[n])
where each of the numbers in the series
is 1 <= nums[i] <= 10000.
Output specification
Show the values of the sorted nodes
according to the given criteria.
Sample Input I
7
4 7 3 2 7 6 3
|
Sample Output I
4 7 3 6 2
|
- The depth of 4 is 0,
- The depth of 3 is 1,
- The depth of 7 is 1,
- The depth of 2 is 2,
- The depth of 6 is 2.
According to our criteria, there is only
one node at depth 0, node 4.
At depth 1 there are only two nodes, 3
and 7, so their order should be 7, 3.
At depth 2 there are two nodes and their
order should be 6, 2.
Sample Input II
12
6 8 2 4 1 2 7 9 4 3 6 5
|
Sample Output II
6 8 2 9 7 4 1 5 3
|
- The depth of 6 is 0,
- The depth of 2 is 1,
- The depth of 8 is 1,
- The depth of 1 is 2,
- The depth of 4 is 2,
- The depth of 7 is 2,
- The depth of 9 is 2,
- The depth of 3 is 3,
- The depth of 5 is 3.
According to our criteria, there is
only one node at depth 0, node 6.
At depth 1 there are only two nodes,
2 and 8, so their order should be 8, 2.
At depth 2 there are four nodes and
their order should be 9, 7, 4, 1.
At depth 3 there are only two nodes
and their order should be 5, 3.
Для отправки решений необходимо выполнить вход.
|