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

Сборники > Data Structures > задача:


50830 - Sorting BST Nodes

Задачи сборника

• 50695 - Longest link between neurons
• 50411 - Sum of the Leaves
• 50677 - The Cottage
• 50795 - Trunk
• 50414 - Traffic
• 50698 - Ayran Delivery
• 50978 - Albanian Coders
• 50699 - Fighting Vampires
• 50830 - Sorting BST Nodes
• 50803 - Sum of the depths in BST
• 50805 - Sum of the weights in a BST
• 50712 - Moon algebra
• 50675 - Kruja Boys
• 50415 - The Scientist
• 50679 - Jetpack Hurdle Jumping
• 50717 - Hurdle Jumping
• 50421 - Repairing road segments

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

Если у вас есть предложения или пожелания по работе 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