BST in C++: Implementation, Methods, Techniques

				
					
#include <bits/stdc++.h> 
#include<iostream>
using namespace std;

// Constructing The Tree
struct Node{
	int data;  
    	struct Node *left;
    	struct Node *right;
    	Node(int val){
        	data=val;
		// Assigning the left and right nodes NULL
        	left=NULL;
        	right=NULL;
    	}
};

// Function To Implement BST
Node* sortedBST(int arr[],int start , int end){
    	if(start>end)
        	return NULL;

	//  Assinging The Mid Value 
    	int mid = (start+end)/2;

	// Assinging The Mid Value As Root Node
    	Node* root = new Node(arr[mid]);

	// Construct Left & Right Subtree
    	root->left = sortedBST(arr, start, mid-1);
    	root->right = sortedBST(arr, mid+1  , end);
    	return root;
}

// Function To Return Minimum Value
Node* min(Node* node)
{
    Node* a = node;
    while (a && a->left != NULL) // Loop To Find Left Leaf
        a = a->left;

    return a;
}

// Function To Delete Node
Node* dNode(Node* root, int key)
{
    if (root == NULL) // Exit Case
        return root;

    if (key < root->data) { // If Element Smaller Than Root
        root->left = dNode(root->left, key);
    }

    else if (key > root->data) { // If Element Higher Than Root

        root->right = dNode(root->right, key);
    }

    else {
        if (root->left == NULL) { // For Node With No CLild
            Node* z = root->right;
            free(root);
            return z;
        }
        else if (root->right == NULL) { // For Node With One CLild
            Node* z = root->left;
            free(root);
            return z;
        }
        Node* t = min(root->right); // For Node With Two CLildren
        root->data = t->data;
        root->right = dNode(root->right, t->data);
    }
    return root;
}

// Function To Print Pre-Order Traversal 
void preorder(Node* root){
    	if(root==NULL)
        	return;
	// Following The N-L-R Rule
    	cout<<root->data<<" ";
    	preorder(root->left);
    	preorder(root->right);
}

int main()
{
	// Assinging The Array.
    	int arr[] ={3,2,1,7,9};
    	int len = sizeof(arr)/sizeof(int);
	// Function Calling
    	Node *root = sortedBST(arr,0,len-1);  
    	// Printing The Data In Preorder
    	Node *root1 = dNode(root,1);
    	cout << "The New BST Is: " << endl;
	preorder(root);
    	return 0;
}