1. Implement the minimum method for binary search trees.
2. Implement the maximum method for binary search trees.
3. Implement the delete method for binary search trees. In the case where the node to be removed has two children, search the right subtree for a replacement value. Do not forget to update the size of the tree when appropriate (including for insertion).
4. Implement the in-order traversal method for binary search trees.
5. Implement the post-order traversal method for binary search trees.
#include
#include
#include
#include "BST.h"
using namespace std;
BST::BST()
{
***********code here**********
}
BST::~BST()
{
***********code here**********
}
//returns the address of the target node (if found)
Node* BST::search(int target)
{
returnsearch(root,target);
}
//method to search for target value in BST
//If node is not present we will return null
Node* BST::search(Node* n, int target)
{
//Tree is empty or value is not found
if (n == nullptr) //if root node is null just return null value
{
returnnullptr;
}
// Value is found
elseif (n->value == target)
{
returnn;
}
//If given valuen is not larger, traverse left.
elseif (n->value > target)
{
returnsearch(n->left, target);
}
//given value larger than current value, traverse right
elseif (n->value <>
{
returnsearch(n->right, target);
}
//else if target is equal to root node just return the root node i.e n.
returnn;
}
Node* BST::minimum()
{
***********code here**********
}
Node* BST::minimum(Node* n)
{
***********code here**********
}
Node* BST::maximum()
{
***********code here**********
}
Node* BST::maximum(Node* n)
{
***********code here**********
}
Node* BST::insertValue(Node* n, int val)
{
//if root node is null
if (n == NULL) {
returnnewNode(val);
}
//if val
if( n->value ==val) {
returnn;
}
//if val>root's data insert in right half
elseif (val > n->value) {
n->right = insertValue(n->right, val);
}
//if root's data is equal to val
elseif (val < n-="">value) {
n->left = insertValue(n->left, val);
}
//return the root node
returnn;
}
void BST::deleteValue(int val)
{
***********code here**********
}
Node* BST::deleteValue(Node* n, int val)
{
***********code here**********
}
//this function uses isBST(root,low,high) as helper function
//to check for binary search tree.
bool BST::isBST(Node* n){
//These low and high are the min. and max. permitted values
//for a particular node
returnisBST(n, INT_MIN, INT_MAX);
}
//Pass low as INT_MIN and high as INT_MAX because
//root of the tree can take any value.
bool BST::isBST(Node* n, int low, int high){
// if n is null , then it is tree
if (n == NULL)
returntrue;
// left child value greater then its root
// then it is not BST
if (n->left != NULL && n->left->value > n->value)
returnfalse;
// rightt child value less then its root
// then it is not BST
if (n->right != NULL && n->right->value < n-="">value)
returnfalse;
// recursive calling
return (isBST(n->left,low,high) || isBST(n->right, low, high));
}
//preOrder traversal method
void BST::preOrder(Node* n, vector &order){
if (n)
{
// Root l R
order.push_back(n); // push node's address
preOrder(n->left, order); // Call on node->left i.e left subtree
preOrder(n->right, order); // Call on node->right i.e right subtree
}
}
void BST::inOrder(Node* n, vector &order)
{
***********code here**********
}
void BST::postOrder(Node* n, vector &order)
{
***********code here**********
}