ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Турниры > CEN303 2013-15 Questions > задача:


15HW-50. 50830 - Sorting BST Nodes

CEN303 2013-15 Questions

Старт: 15.дек.2013 в 14:00:00
Финиш: 15.дек.2013 в 19:00:00
Турнир завершён!
• Турнирная таблица

Задачи турнира

• 14-FallResit-20. 50488 - Connecting...
• 15FE-01. 50851 - Repeated Numbers
• 15FE-01. 50838 - Balanced Numbers
• 15FE-04. 50997 - Dynamic Knights
• 15HW-10. 50826 - Olive Containers
• 15HW-30. 50828 - Arranging Time ...
• 15HW-40. 50676 - Cinema Millennium
• 15HW-40. 50829 - Decode an Image
• 15HW-50. 50830 - Sorting BST ...
• 15HW-60. 50678 - The Jumping Rabbit
• 15MdE-10. 50802 - Comparing Exams
• 15MdE-20. 50803 - Sum of the dept...
• 15MdE-40. 50805 - Sum of the weig...
• 15PrE-10. 50816 - Largest Sum Path
• 15PrE-20. 50817 - The Knight Move
• 15PrE-30. 50818 - Depth Limited BST
• 15PrE-40. 50819 - Linked Numbers

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
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

  1. The depth of 4 is 0,
  2. The depth of 3 is 1,
  3. The depth of 7 is 1,
  4. The depth of 2 is 2,
  5. 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

  1. The depth of 6 is 0,
  2. The depth of 2 is 1,
  3. The depth of 8 is 1,
  4. The depth of 1 is 2,
  5. The depth of 4 is 2,
  6. The depth of 7 is 2,
  7. The depth of 9 is 2,
  8. The depth of 3 is 3,
  9. 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.



Для отправки решений необходимо выполнить вход.

www.contester.ru