HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Contests > CEN303 2013-15 Questions > problem:


15HW-50. 50830 - Sorting BST Nodes

CEN303 2013-15 Questions

Start: Dec.15.2013 at 02:00:00 PM
Finish: Dec.15.2013 at 07:00:00 PM
The contest is finished!
• Contest scoreboard

Contest problems

• 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

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

  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