C++ or Java Difference of Pairs on a BST : Write a method/function that outputs

Question

C++ or Java

Difference of Pairs on a BST: Write a method/function that outputs two, x and y, in a given BST, where the key values of x and y differ by a given integer k. Recall that we had given the following algorithm in lecture that on an sorted input array A and given value k returns two indices i and j, where A[i] – A[j] = k, or report error if such i and j do not exist:

i1; j2;

nlength[A] //assuming  of A start with 1

while (jn and in)

d A[i] – A[j]

if (d==k)

return (i, j)

if (d

i++

else

j++

return (-1, -1) //To indicate no such i and j exists.        

Now you just need to adapt the above algorithm to work on a BST and return two (references/pointers of) nodes (not just the values) in the BST with the desired property. Since the above algorithm runs in O(n) time on an sorted array ofnelements, the algorithm entailed by your method/function should also run in O(n)time.

Explanation / Answer

Code in Java:

// A is the list of all nodes sorted by their valus
void findPair(Node A, Node i, Node j, int k)
{
   i = A; // first or head node
   j = A.next;

   int n = getSize(); // gets the number of total nodes

   while(i != null && j != null)
   {  
       int d = i.value – j.value;
       if(d == k)
           return;

       if(d < k)
           i = i.next;
       else
           j = j.next;
   }

   i = null;
   j = null;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.