# CS301 Data Structures Assignment 3 Solution Fall 2012

A “Binary Search Tree” (BST) is a type of binary tree with the following property:

“Items in the left subtree are smaller than the root, and items in the right subtree are greater than the root”.

Consider the following Binary Search Tree (BST):

Keeping in mind the property of Binary Search Tree (BST), Write a program in C++ which stores the above tree (BST) in computer memory and performs the following operations on the tree:

1. Count total number of nodes in the tree
2. Count number of leaf nodes in the tree
3. Display value of each node using any of the traversal methods

Solution Guidelines:

Your Program should contain a BST class which should include the following functions:

• insert_nodes( ) // to insert all nodes in the BST.
• count_nodes( ) // to count total number of nodes in the tree
• count_leaft_nodes( ) // to count number of leaf nodes in the tree
• display( ) // to display nodes’ values on screen using any traversal methods (Preorder, Inorder, Postorder)

In main ( ) function, create an object of type “BST” and call above functions one by one against each operation.

Solution:

```#include<iostream.h>
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
node *left;
node *right;
};

node *tree=NULL;
node *insert(node *tree,int ele);

void preorder(node *tree);
void inorder(node *tree);
void postorder(node *tree);
int count=1;

void main()
{
clrscr();
int ch,ele;
do
{
clrscr();
cout"ntaa1----INSERT A NODE IN A BINARY TREE.aa";
cout"ntaa2----PRE-ORDER TRAVERSAL.aa";
cout"ntaa3----IN-ORDER TRAVERSAL.aa";
cout"ntaa4----POST-ORDER TRAVERSAL.aa";
cout"ntaa5----EXIT.aa";
cout"ntaaENTER CHOICE::aa";
cin>>ch;
switch(ch)
{
case 1:
cout"ntaaENTER THE ELEMENT::aa";
cin>>ele;
tree=insert(tree,ele);
break;

case 2:
cout"ntaa****PRE-ORDER TRAVERSAL OF A TREE****aa";
preorder(tree);
break;

case 3:
cout"ntaa****IN-ORDER TRAVERSAL OF A TREE****aa";
inorder(tree);
break;

case 4:
cout"ntaa****POST-ORDER TRAVERSAL OF A TREE****aa";
postorder(tree);
break;

case 5:
exit(0);
}
}while(ch!=5);
}

node *insert(node *tree,int ele)
{
if(tree==NULL)
{
tree=new node;
tree->left=tree->right=NULL;
tree->data=ele;
count++;
}
else
if(count%2==0)
tree->left=insert(tree->left,ele);
else
tree->right=insert(tree->right,ele);
return(tree);
}

void preorder(node *tree)
{
if(tree!=NULL)
{
couttree->data;
preorder(tree->left);
preorder(tree->right);
getch();
}
}

void inorder(node *tree)
{
if(tree!=NULL)
{
inorder(tree->left);
couttree->data;
inorder(tree->right);
getch();
}
}

void postorder(node *tree)
{
if(tree!=NULL)
{
postorder(tree->left);
postorder(tree->right);
couttree->data;
getch();
}

}

```