Loading...
Loading...
Loading...
Ankit runs a small online store. Each day he notes the profit in rupees, which is negative on a day with a loss. He inserts the n daily amounts, in the given order, into an empty binary search tree.
Print the smallest amount and the number of nodes on the walk from the root to it. Then print the largest amount and the number of nodes on the walk from the root to it. Count the root and the final node too.
Example 1
Input
5 50 30 70 20 40
Output
20 3 70 2
Going left from 50 visits 50, 30 and 20. Going right visits 50 and 70.
Example 2
Input
4 -5 -8 3 -20
Output
-20 3 3 2
Losses are negative. The smallest is -20 after -5 and -8. The root -5 has right child 3 and nothing beyond it.
Try the problem first. Open one hint at a time.
Every value smaller than a node lives in its left subtree.
So the smallest value is reached by going left from the root until there is no left child.
The largest is the same walk to the right. Count every node you stand on, including the root.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor