augmenting bst - is there exist pair (a,b) of numbers such that |b-a| = d?
By "in linear time I can find that pair" I assume you are using two-pointer technique, that using 2 pointers to traversal the array, trying to reduce the gap to the target by advancing one of the pointer.

An in-order traversal of BST outputs all values in order in linear time. So you can apply your linear-time algorithm similarly on BST, only the pointers advancing to the in-order next node.