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 ofn elements, the algorithm entailed by your method/function should also run in O(n) time.

Explanation / Answer

Algorithm:

1) Store the nodes of BST in an array by using inorder traversal.
2) Apply the algorithm discussed in Lecture.

C++ Code:

class Node{
public:
   int value;
   Node * left;
   Node * right;
   Node(){
       value=0;
       left=NULL;
       right=NULL;
   }
};

void inorder(Node * bst,vector<Node* > * vec){
   if(bst!=NULL){
       inorder(bst->left,vec);
       vec->push_back(bst);
       inorder(bst->right,vec);
   }
}

pair<Node*,Node* > differk(Node * bst,int k){
   vector<Node* > * vec;
   inorder(bst,vec);
   int l=vec->size();
   int i=0;
   int j=1;
   while(i<l && j<l){
       int d=(vec->at(j)->value)-(vec->at(i)->value);
       if(d==k){
           pair<Node*,Node* > p;
           p.first=vec->at(i);
           p.second=vec->at(j);
           return p;
       }
       else if(d>k){
           i++;
       }
       else{
           j++;
       }
   }
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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