@himanshu41 Hi, thank you for your brilliant solution! as you said, the complexity of your solution is O(n + k). Since k < n, O(n + k) < O(2n) ~ O(n). So I think you could safely claim that the complexity of your solution is O(n) and work for the follow up.
Closest Binary Search Tree Value II