Full C++ Code Difference of Pairs on a BST : Write a method/function that output

Question

Full C++ Code

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<k)

i++

else

j++

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

Explanation / Answer

class Node
{
public:
int value;
Node * left;
Node * right;
Node(){
value = 0;
left = 0;
right = 0;
}
};
void inorder(Node * bst, vector<Node* > * vec)
{
if (bst != 0)
{
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 F
• Subjects

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