Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Prepared by Ibrahim Mesecan.
Average Depth
The depth of a node in trees, is the number of steps to reach to the node from the root.
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). Calculate the average depth of the tree.
Input specification
You will be first given a number (n) the number of numbers where 1 ≤ n ≤ 10000. Then you will be
given n space separated numbers (nums[n]) where each of the number in the series is 1 ≤ nums[i] ≤ 10000.
Output specification
Calculate and show the average depth of the BST with three digits precision.
Sample Input I
12
6 8 2 4 1 2 7 9 4 3 6 5
|
Sample Output I
1.778
|
Output I Explanation
The depth of 6 is 0,
The depth of 2 is 1,
The depth of 8 is 1,
The depth of 4 is 2,
The depth of 7 is 2,
The depth of 3 is 3, etc.
Each of the numbers: 2, 4, and 6 appears twice. Thus there are normally 9 numbers in the BST.
Sum of the depths is 16, and thus the average is 16/9= 1.778
Для отправки решений необходимо выполнить вход.
|