BST.cpp

#include "BST.h"

node* BST::search(int x)
{
	if (x == root->data)
	{
		return root;
	}
	node* temp = root;
	while (temp)
	{

		if (x < temp->data)
		{
			temp = temp->leftchild;
		}
		else if (x > temp->data)
		{
			temp = temp->rightchild;
		}
		else if (x == temp->data)
		{
			return temp;
		}
	}
}




void BST::outleftandright() {
	node* temp = root;
	cout << "LEFT\n";
	while (temp)
	{
		cout << temp->data << endl;
		temp = temp->leftchild;
	}
	temp = root;
	cout << "Right\n";
	while (temp)
	{
		cout << temp->data << endl;
		temp = temp->rightchild;
	}

}

BST::BST()
{
	root = nullptr;
}

node* BST::rooter()
{
	return root;
}

void BST::insertion(int data)
{
	if (root == nullptr)
	{
		root = new node;
		root->data = data;
		root->leftchild = nullptr;
		root->rightchild = nullptr;
	}
	else {
		node* temp = root;
		while (true)
		{

			if (data < temp->data)
			{

				if (temp->leftchild == nullptr)
				{
					temp->leftchild = new node;
					temp->leftchild->parent = temp;
					temp = temp->leftchild;

					temp->data = data;
					temp->leftchild = nullptr;
					temp->rightchild = nullptr;
					break;
				}
				temp = temp->leftchild;
			}
			else if (data >= temp->data)
			{
				if (temp->rightchild == nullptr)
				{
					temp->rightchild = new node;
					temp->rightchild->parent = temp;
					temp = temp->rightchild;
					temp->data = data;
					temp->leftchild = nullptr;
					temp->rightchild = nullptr;
					break;
				}
				temp = temp->rightchild;
			}
		}

		temp->data = data;
		temp->leftchild = nullptr;
		temp->rightchild = nullptr;
	}

}

BST.h

#pragma once
#include <iostream>
using namespace std;
struct node {
	int data;
	node* leftchild, * rightchild, * parent;
};

class BST {
private:
	node* root;

public:
	BST();
	node* rooter();

	void insertion(int);
	void outleftandright();
	node* search(int x);

};

ConsoleApplication1.cpp

#include "BST.h"
#include "help.h"

int main()
{
	BST b1;

	b1.insertion(5);
	b1.insertion(3);
	b1.insertion(2);
	b1.insertion(5);

	b1.insertion(7);
	b1.insertion(9);


	printInorder(b1.rooter());

}

help.cpp

#pragma once
#include "help.h"


void printInorder(node* root)
{
	if (root == nullptr)
		return;

	/* first recur on left child */
	printInorder(root->leftchild);

	/* then print the data of node */
	cout << root->data << " ";

	/* now recur on right child */
	printInorder(root->rightchild);
}


node*minimum(node* b1)
{
while (b1->leftchild != nullptr)
{
	b1 = b1->leftchild;
}
return b1;
}

node* maximum(node* temp)
{
	
	while (temp->rightchild != nullptr)
	{
		temp = temp->rightchild;
	}
	return temp;
	

}

node* successor(BST b1, int x)
{
	node* temproot = b1.search(x);
	node* temproot1 = temproot;
	if (temproot->rightchild != nullptr)
	{
		return minimum(temproot->rightchild);
	}
	else
	{
		node* y = temproot->parent;
		while (y != nullptr && temproot == y->rightchild)
		{
			temproot = y;
			y = temproot->parent;
		}
		if (y == nullptr)
		{
			return maximum(temproot1);
		}
		else {
			return y;
		}
	}
}

node* predecessor(BST b1, int x)
{

	node* temproot = b1.search(x);
	node* temproot1 = temproot;
	if (temproot->leftchild != nullptr)
	{
		return maximum(temproot->leftchild);
	}
	else
	{
		node* y = temproot->parent;
		while (y != nullptr && temproot == y->leftchild)
		{
			temproot = y;
			y = temproot->parent;
		}
		if (y == nullptr)
		{
			return minimum(temproot1);
		}
		else {
			return y;
		}
	}
}

help.h

#include "BST.h"


void printInorder(node* root);

node* minimum(node* b1);

node* maximum(node* temp);



node* successor(BST b1, int x);

node* predecessor(BST b1, int x);