0: 1, 21: 3, 42: 5, 63: -1, 74: 8, 95: -1, 106: 11, 12 0 551 272 813 34 395 706
ID: 3732563 • Letter: 0
Question
0: 1, 21: 3, 42: 5, 63: -1, 74: 8, 95: -1, 106: 11, 120 551 272 813 34 395 706 937 148 319 4210 7411 9112 98
Q2-50 pts) A binary search tree (BST) is a binary tree in which the data for an internal node is greater than or equal to the data of its left child node and lower than or equal to the data of its right child node. Consider the code for the binary tree given to you for this question. Add code in the blank space provided for the member function checkBST) in the BinaryTree class. This member function should check whether the binary tree input by the user (in the form of the edge and data information stored in two separate files) is a binary search tree You are provided a sample of two files that constitute the edges and data for a binary tree that is also a binary search tree. You could validate your code with these two files. The main function of the code giver to you is already updated to input the above two files. Your task is only to implement the checkBSTO function and test its working through files that represent the edges and data for a binary tree. To test your code, come up with two binary tree of at least 12 nodes as follows: (i) A binary tree that is also a BST with the data of the nodes setup in such a way that the data for an internal node is greater than or equal to its left child and lower than or equal to its right child (ii) In the binary tree that you came up with for(), change the data of the nodes in such a way that for at least one internal node, the BST requirement is violated so that the binary tree is not a BST Prepare the input files (edges and data files) for the two scenarios above and test your code with these files
Explanation / Answer
int checkBST(struct node* node)
{
if (node == NULL)
return 1;
if (node->left!=NULL && max(node->left) > node->data)
// max(node->left) finds maximum of left subtree
return 0;
if (node->right!=NULL && min(node->right) < node->data)
//min(node->right) finds minimum of right subtree
return 0;
if (!checkBST(node->left) || !checkBST(node->right))
return 0;
return 1; // if all the above conditions are not met then it is a BST
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.