C++ Program to implement Depth-first search in binary tree

In depth-first order, we always attempt to visit the node farthest from the root node that we can, but with the caveat that it must be a child of a node we have already visited. Unlike a depth-first search on graphs, there is no need to remember all the nodes we have visited, because a tree cannot contain cycles. Pre-order is a special case of this. See depth-first search for more information.

For more visit : http://en.wikipedia.org/wiki/Binary_tree

 #include<iostream.h>
#include<conio.h>
struct node
{
int info;
node *left;
node *right;
}*root;
void insert(int,node*);
void insert(int item)
{
if(root!=NULL)
insert(item, root);
else
{
root=new node;
root->info=item;
root->left=NULL;
root->right=NULL;
}
}
void insert(int item, node *leaf)
{
if(item< leaf->info)
{
if(leaf->left!=NULL)
insert(item,leaf->left);
else
{
leaf->left=new node;
leaf->left->info=item;
leaf->left->left=NULL;
leaf->left->right=NULL;
}
}
else if(item>=leaf->info)
{
if(leaf->right!=NULL)
insert(item, leaf->right);
else
{
leaf->right=new node;
leaf->right->info=item;
leaf->right->left=NULL;
leaf->right->right=NULL;
}
}
}
int DFS(node *leaf,int search)
{
static found =0;
if(leaf!=NULL)
{
if(leaf->info==search)
found=1;
DFS(leaf->left,search);
DFS(leaf->right,search);
cout<<" "<<leaf->info;
}
return found;
}
void main()
{
clrscr();
int op;
int item;
while(op!=3)
{
cout<<"\nSelect Option\n1.Insert item\n2.Search item\n3.exit\n";
cin>>op;
switch(op)
{
case 1:
cout<<"Enter the item to insert in tree :";
cin>>item;
insert(item);
break;
case 2:
cout<<"Enter item to search :";
cin>>item;
cout<<" DFS :";
if(DFS(root,item))
cout<<"\t Item Found\n";
else
cout<<"\t Item Not Found\n";
break;
case 3:
cout<<"Press any to exit";
break;
default:
cout<<"Invalid option";
}
getch();
}

}