Find the next smallest number for a given number

In an unsorted array, given a number 'x',
find the next smallest number.
The number 'x' does exist in the array.
Array {62,50,91,32,60,63,17,36,55,61}
Num = 62
Result = 61

Num = 50
Result = 36

Approach:

Sorting is not a solution, since it will be O(N^2) or atleast O(N log N). 

Create a Binary Search Tree and find the number 'X'. Once found, fetch the right most node of its left subtree. Thats the required element.

Solution