Question

1. Recall that in a binary search tree, at every node, all elements to the left of the node have a smaller key, and all elements to the right of a node have a larger key. Write a program called that takes two parameters: a pointer to a binary search tree node, and an int parameter called min which will print all the elements bigger than the specified value, min. Your program should allow the user to enter data (integer) from standard input and construct a binary search tree. Make your program as ecient as possible and explain its worst-case asymptotic running time.

        void PrintElements(BinarySearchTree *node, int min)
        Input: A binary search tree node, representing the root of a BST
        Output: Does not return anything, but prints all node values that are bigger than min
   

Answer 1

C++ code is given below:

#include <iostream>
using namespace std;
// Node structure of BST
struct BinarySearchTree
{
int data;
struct BinarySearchTree *left, *right;
};
// function to insert the node into the BST
struct BinarySearchTree* insert(struct BinarySearchTree* node, int val)
{
if (node == NULL) {
struct BinarySearchTree *newNode =
(struct BinarySearchTree *)malloc(sizeof(struct BinarySearchTree));
newNode->data = val;
newNode->left = newNode->right = NULL;
return newNode;
}
if (val < node->data)
node->left = insert(node->left, val);
else if (val > node->data)
node->right = insert(node->right, val);
return node;
}
// function to print the node of the BST with value greater than min
void PrintElements(struct BinarySearchTree *node, int min) {
if(node == NULL) // return if node is null
return;
if(node->data > min) // we go to the left subtree if and only if the node value is greater than min
PrintElements(node->left,min);
if(node->data > min) // we print the node value if it is greater than min
cout<<node->data<<" ";
PrintElements(node->right,min); // otherwise we go to the right subtree
}
int main() {
struct BinarySearchTree *root = NULL;
/* Let's create following BST
5
/ \
3 7
/ \ / \
2 4 6 8 */
root = insert(root,5);
insert(root,5);
insert(root,3);
insert(root,2);
insert(root,4);
insert(root,7);
insert(root,6);
insert(root,8);
// printing all the nodes with value greater than 5 in the above BST
cout<<"Node values greater than 5: ";
PrintElements(root, 5);

return 0;
}

Sample input tree:
  5
/ \
3 7
/ \ / \
2 4  6 8

Sample output:
Node values greater than 5: 6 7 8

worst-case asymptotic running time :
In the worst case, all the nodes of the Binary Search Tree would be traversed. So, the worst time running time would be O(N) where N is the number of nodes present in the Binary search tree.

Screenshot of code:

If the answer helped please upvote, it means a lot and for any query please comment.