// Complete the C++ function and its recursive helper to determine whether the t
ID: 3729618 • Letter: #
Question
// Complete the C++ function and its recursive helper to determine whether the tree rooted at root is a binary search tree.
#include <iostream>
// Code goes here pt1
using namespace std;
class Node {
public:
Node *left;
Node *right;
int data;
Node(int d) {
data = d;
left = nullptr;
right = nullptr;
}
};
bool validateBst(Node *root, Node *min, Node *max) {
// Code goes here pt2
}
bool validateBst(Node *root) {
// Code goes here pt3
}
void deleteTree(Node *root) {
if (!root) {
return;
}
deleteTree(root->left);
deleteTree(root->right);
delete root;
}
int main() {
Node *root1 = new Node(8);
root1->left = new Node(7);
root1->right = new Node(12);
root1->left->left = new Node(3);
root1->left->right = new Node(9);
root1->right->left = new Node(10);
root1->right->right = new Node(15);
Node *root2 = new Node(8);
root2->left = new Node(4);
root2->right = new Node(12);
root2->left->left = new Node(3);
root2->left->right = new Node(6);
root2->right->left = new Node(10);
root2->right->right = new Node(15);
Node *root3 = nullptr;
Node *root4 = new Node(42);
Node *root5 = new Node(8);
root5->left = new Node(7);
root5->right = new Node(12);
root5->left->left = new Node(3);
root5->left->right = new Node(1);
root5->right->left = new Node(10);
root5->right->right = new Node(15);
cout << validateBst(root1) << endl;
cout << "Expected: 0" << endl;
cout << validateBst(root2) << endl;
cout << "Expected: 1" << endl;
cout << validateBst(root3) << endl;
cout << "Expected: 1" << endl;
cout << validateBst(root4) << endl;
cout << "Expected: 1" << endl;
cout << validateBst(root5) << endl;
cout << "Expected: 0" << endl;
deleteTree(root1);
deleteTree(root2);
deleteTree(root3);
deleteTree(root4);
deleteTree(root5);
return 1;
}
Explanation / Answer
bool validateBst(Node *root, Node *min=NULL, Node *max=NUL) {
{
if (root == NULL)
return true;
// if left node exist that check it has
// correct data or not
if (min!= NULL and root->data < min->data)
return false;
// if right node exist that check it has
// correct data or not
if (max!= NULL and root->data > max->data)
return false;
// check recursively for every node.
return validateBst(root->left, min, root) and
validateBst(root->right, root, max);
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.