All problems

Median Finish Time

Medium · tree dfs

After a fun run, the organisers file every runner's finish time (in seconds) in a binary search tree, so that root holds all the times. They want the median finish time: if you wrote all the times in increasing order, the one in the middle.

When the number of runners is even there are two middle times. Return the smaller of the two. If nobody finished (the tree is empty), return -1.

In a binary search tree, for every node all times in its left subtree are smaller and all times in its right subtree are larger. All times are distinct.

Examples

Example 1

Input: root = [40, 20, 60, 10, 30, 50, 70]

Output: 40

Seven times in order are 10, 20, 30, 40, 50, 60, 70. The middle one is 40.

Example 2

Input: root = [50, 30, 80, 20, 40]

Output: 40

The times in order are 20, 30, 40, 50, 80. The middle one is 40.

Example 3

Input: root = [9, 4, 12, 2]

Output: 4

The times in order are 2, 4, 9, 12. The two middle times are 4 and 9, and the smaller one is returned.

Constraints

• The number of nodes is in the range [0, 2000].
• 0 <= Node.val <= 10^6, and all values are distinct.
• The tree is a valid binary search tree.