BST (level order,preorder,inorder and postorder traversal).

BST (level order,preorder,inorder and postorder traversal).

//Program for (1).BFS. Level order traversal.
//(2). DFS(Preorder,Inorder,Postorder).
#include <iostream>
#include <queue>
using namespace std;
struct node
{ int data; node*left ; node*right ;//data,left child pointer,right ch ptr.
};

node* makenode(int data)
{  //this function creates a new node pointer,makes that pointer point to a node,sets node values  and returns that pointer.
    node* x= new node();
  x->left = NULL;
  x->right=NULL;
  x->data=data;
  return x;
}
node* insert(node* root,int data)
{
if(root==NULL) { root = makenode(data); return root ;}
//since root in main is local variable it won't be modified,so we return this root value(which is address to a node in heap) and store it in the root of main function
else if(data<=root->data)
{ root->left=insert(root->left,data);
  return root; 
}
else 
{ root->right=insert(root->right,data);// recursive call
  return root; }
}
//the function below  performs level order traversal i.e BFS 
//using a queue to put the nodes in, as soon as a node is taken out,it's children are pushed in.
void levelorder(node* root)
{ if(root==NULL){ return; }
  queue<node*> q;
  q.push(root);
  while(!q.empty()){ 
      node* current = q.front();
      cout<<current->data<<" ";
  if(current->left!=NULL) { q.push(current->left);}
  if(current->right!=NULL) { q.push(current->right);}
  q.pop(); //removing the first element from queue
  }
}
void preorder(node* root)
{if(root == NULL) {return;}
cout<<root->data<<" ";
preorder(root->left);
preorder(root->right);
}
void inorder(node* root) //prints the sorted order
{
if(root == NULL) {return;}
inorder(root->left);
cout<<root->data<<" ";
inorder(root->right);
}
//in this way postorder function can also be made
int main()
{  node* root=NULL;
   root = insert(root,20);
   root = insert(root,35);
   root = insert(root,25);
   root = insert(root,15);root = insert(root,30);root = insert(root,40);
   levelorder(root);cout<<endl;
   preorder(root);cout<<endl;inorder(root);
   return 0;
}