0
$\begingroup$

How to check if exist pair $(a,b)$ of numbers in BST such that $|a-b| = d$, where $d$ is given.
Example:
contain of tree: $1, 4, 5, 3, 8, 45, 532$
$d=5$,
answer: $yes$, there is pair $(5,8)$
$d=52$
answer: $no$.

I can solve it when number are in array - then I sort them, and in linear time I can find that pair. Neverthelress I can't idea how to augment BST in this task.
Can you give me a hint ?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Ok, I understand you, but pesimistic time is O(n). Is there solution in O(logn) ? $\endgroup$ – M.Swe Aug 31 '15 at 11:17
  • $\begingroup$ You can use interval tree if it is working $\endgroup$ – Evil Aug 31 '15 at 12:23
  • $\begingroup$ A BST might well be linear, if the elements were inserted in say, increasing order. So, if you can't find a linear-time solution for an array, you can't find one for a BST. $\endgroup$ – saulspatz Aug 31 '15 at 14:59
  • $\begingroup$ even point query in balanced BST is just like binary search in sorted array. (possibly with additional cumulative properties). I don't think this helps to find an O(logN) query algorithm. $\endgroup$ – Terence Hang Aug 31 '15 at 16:18
  • $\begingroup$ one possible direction may be to store difference between adjacent values in segment tree. then the range sum query is just the difference between two values in orginal. But I haven't got any sub-linear time solution from this. $\endgroup$ – Terence Hang Aug 31 '15 at 16:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.