Binary Search Tree

#include <iostream>
using namespace std;
class Node {
public:
  int data;
  Node *left;
  Node *right;

  // Constructor
  Node(int data) {
    this->data = data;
    this->left = NULL;
    this->right = NULL;
  }
};

Node *insert(Node* &root, int data) {
  if (root == NULL) {
    root = new Node(data);
    return root;
  }
  if (data > root->data) {
    root->right = insert(root->right, data);
  } else {
    root->left = insert(root->left, data);
  }
  return root;
}
// Inorder Traversal gives us sorted order list for BST
void inorder(Node *root) {
  if (root == NULL) {
    return;
  }
  inorder(root->left);
  cout << root->data << " ";
  inorder(root->right);
}
void preorder(Node *root) {
  if (root == NULL) {
    return;
  }
  cout << root->data << " ";
  inorder(root->left);
  inorder(root->right);
}
void postorder(Node *root) {
  if (root == NULL) {
    return;
  }
  postorder(root->left);
  postorder(root->right);
  cout << root->data << " ";
}
int height(Node *root) {
  if (root == NULL) {
    return 0;
  }
  int lHeight = height(root->left);
  int rHeight = height(root->right);

  return max(lHeight, rHeight) + 1;
}
bool search(Node *root, int key) {
  bool ans = false;
  if (root == NULL) {
    return ans;
  }
  // Data exist condition
  if (key == root->data) {
    cout << "Data Found!!" << endl;
    return true;
  }
  if (key > root->data) {
    search(root->right, key);
  } else {
    search(root->left, key);
  }
  return ans;
}

int smallest(Node *root) {
  // simple concept
  while (root->left != NULL) {
    root = root->left;
  }
  return root->data;
}
int largest(Node *root) {
  // simple concept
  while (root->right != NULL) {
    root = root->right;
  }
  return root->data;
}
int totalNodes(Node *root) {
  if (root == NULL) {
    return 0;
  }
  int lNodes = totalNodes(root->left);
  int rNodes = totalNodes(root->right);

  return lNodes + rNodes + 1;
}
// The nodes which are not leaf nodes -> Internal Nodes
int totalInternalNode(Node *root) {
  if (root == NULL) {
    return 0;
  }
  if (root->left == NULL && root->right == NULL) {
    return 0;
  }
  return (totalInternalNode(root->left) + totalInternalNode(root->right) + 1);
}
// The nodes which are leaf nodes -> External Nodes
int totalExternalNode(Node *root) {
  // Simple Solution
  // return (totalNodes(root)-totalInternalNode(root));

  // Complex Solution or Traditional Solution
  if (root == NULL) {
    return 0;
  }
  if (root->left == NULL && root->right == NULL) {
    return 1;
  }
  return (totalExternalNode(root->left) + totalExternalNode(root->right));
}
int sumOfNodes(Node *root) {
  if (root == NULL) {
    return 0;
  }
  return (sumOfNodes(root->right) + sumOfNodes(root->left) + root->data);
}

Node* deleteFromBST(Node* root, int data){
	//Base case
	if(root == NULL){
		return root;
	}
	if(root->data == data){
		// Main deletion operation will be handled here
		// Here we will handle 3 cases

		// Case 1: 0 Child
		if(root->right==NULL && root->left==NULL){
			// Perform delete to free the memory
			delete root;
			// Make that node points to NULL
			return NULL;
		}
		// Case 2: 1 Child
		// Here comes two sub-cases
		// Sub-Case 1: Right Child Exists
		if(root->right != NULL && root->left == NULL){
			// Store the right child 
			Node* temp = root->right;
			// Perform delete
			delete root;
			// Return the right child 
			return temp;
		}
		// Sub-Case 2: Left Child Exists
		if(root->right == NULL && root->left != NULL){
			// Store the left child 
			Node* temp = root->left;
			// Perform delete
			delete root;
			// Return the right child 
			return temp;
		}
		// Case 3: 2 Children
		if(root->left != NULL && root->right != NULL){
			// Step No. 1: We have to find the minimum value of right subtree
			// Or we can find out the maximum value of left subtree
			// any one of these will work fine. I will go for the first one.
	
			// Find the minimum value from right subtree
			int minValue = smallest(root->right);
			// Step No. 2: Copy that value to the present node
			root->data = minValue;
			//  Step No. 3: 
			// Now the data is successfully copied so we don't need that node
			// That's why we need to delete it from the right subtree because
			// we know that it is present on the right subtree
			root->right = deleteFromBST(root->right,minValue);
			// Step No.4: Now return the root for final operation
			return root;
		}
	}
	// If value is greater than root->data
	else if(data > root->data){
		//We are calling the function for the right sub-tree
		root->right = deleteFromBST(root->right, data);
		return root;
	}
	// If value is lesser than root->data
	else{
		//We are calling the function for the left sub-tree
		root->left = deleteFromBST(root->left, data);
		return root;
	}
}

int main() {
  /*

                               6
                             /   \
                            4	  9
                          /  \     \
                         1	  5	   11
  */

  Node *root = NULL;
  insert(root, 6);
  insert(root, 4);
  insert(root, 9);
  insert(root, 1);
  insert(root, 5);
  insert(root, 11);
  inorder(root);
  cout << endl;
  preorder(root);
  cout << endl;
  postorder(root);
  cout << endl;
  cout << "Height of the tree is: " << height(root) << endl;
  search(root, 4);
  if (!search(root, 10)) {
    cout << "Data doesn't exist!!" << endl;
  }
  cout << smallest(root) << endl;
  cout << largest(root) << endl;
  cout << totalNodes(root) << endl;
  cout << totalInternalNode(root) << endl;
  cout << totalExternalNode(root) << endl;
  cout << sumOfNodes(root) << endl;
  root = deleteFromBST(root, 4);
  inorder(root);
  cout<<endl;
  cout<<totalNodes(root)<<endl;
}