CSCI 221 BST

Q1 : Finding the size of the BST

Implement the following pseudo code:

If root is NULL then return 0
Else call the Size method recursively with the left of the root and the right of the root.

Q2 : Finding the height of the BST

Implement the following pseudo code:

If root is NULL then return 0
Else call the Height method recursively with the left of the root and the right of the root.
If the height of the left part of the BST is greater than the right part of the BST, then return height of left + 1.
Else return height of the right + 1.

Q3 : Finding a given value in the BST

Implement the following pseudo code:

If root is NULL then return false.
If target is equals to root, return true.
If target is less than the root, call the find method recursively with the left child of the root.
Else call the find method recursively with the right child of the root.

Q4 : Finding the minimum and maximum values in the BST

Write two methods,
minimumValue
maximumValue,

that return the the minimum and the maximum values that stored in the BST. Hint: InaBST, the values are stored in the order of

leftChildNode < rootNode< rightChildNode

Starter Code

#include < iostream>
using namespace std;
struct node {
int data;
struct node* left;
struct node* right;
};
struct node* newNode(int data){
struct node* node = new struct node;
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
void insert(struct node** rootRef, int data){
if(*rootRef == NULL){
*rootRef = newNode(data);
}else{
if(data <= (*rootRef)->data){
insert( &((*rootRef)->left), data);
}else{
insert( &((*rootRef)->right), data);
}
}
}
void printInOrder(struct node* root){
if(root == NULL) return;
printInOrder(root->left);
cout << root->data << " ";
printInOrder(root->right);
}
void printPreOrder(struct node* root){
if(root == NULL) return;
cout << root->data << " ";
printPreOrder(root->left);
printPreOrder(root->right);
}
void printPostOrder(struct node* root){
if(root == NULL) return;
printPostOrder(root->left);
printPostOrder(root->right);
cout << root->data << " ";
}

// TODO:
// Q1: Finding the size of BST
// int size(struct node* root){}
// Q2: Finding the height of BST
// int height(struct node* root){}
// Q3: Finding a given value in BST
// bool findValue(struct node* root, int target){}
// Q4: Finding the max and the min values in BST
// int findMaxValue(struct node* root){}
// int findMinValue(struct node* root){}

int main() {
struct node* root = NULL;
insert(&root, 70);
insert(&root, 90);
insert(&root, 60);
cout << "In-order: ";
printInOrder(root);
cout << "n";
cout << "Pre-order: ";
printPreOrder(root);
cout << "n";
cout << "Post-order: ";
printPostOrder(root);
cout << "n";
return 0;
}