Question

In C++:

Write a binary search tree and include the functions to find the number of nodes and the height of the tree. Test your code in main. Print the post-order, in-order and pre-order traversal.

Answer 1

#include<bits/stdc++.h>

using namespace std;

class BST

{

int data;

BST *left, *right;

public:

BST(){}

BST(int value)

{

data = value;

left = right = NULL;

}

  

BST* Insert(BST *root, int value)

{

if(!root)

{

return new BST(value);

}

  

if(value > root->data)

{

root->right = Insert(root->right, value);

}

else

{

root->left = Insert(root->left, value);

}

return root;

}

void Inorder(BST *root)

{

if(!root)

{

return;

}

Inorder(root->left);

cout << root->data << " ";

Inorder(root->right);

}

void Preorder(BST *root)

{

if(!root)

{

return;

}

cout << root->data << " ";

Preorder(root->left);

Preorder(root->right);

}

void Postorder(BST *root)

{

if(!root)

{

return;

}

Postorder(root->left);

Postorder(root->right);

cout << root->data << " ";

}

int Count(BST *root)

{

if(root == NULL){

return 0;

}

else{

return 1 + Count(root->left) + Count(root->right);

}

}

};

int main()

{

BST *root = NULL;

int value;

int choice;

BST bst;;

  

while (1)

{

cout<<"\n\n1.Insert Node"<<endl;

cout<<"2.Count Nodes"<<endl;

cout<<"3.Inorder Traversal"<<endl;

cout<<"4.Preorder Traversal"<<endl;

cout<<"5.Postorder Traversal"<<endl;

cout<<"6.Quit"<<endl;

cout<<"Enter your choice : ";

cin>>choice;

switch(choice)

{

case 1:

cout<<"\nEnter the number to be inserted : ";

cin>>value;

root = bst.Insert(root, value);

break;

case 2:

cout << "\nTotal no of nodes : " << bst.Count(root);

break;

case 3:

cout<<"Inorder Traversal of BST:"<<endl;

bst.Inorder(root);

cout<<endl;

break;

case 4:

cout<<"Preorder Traversal of BST:"<<endl;

bst.Preorder(root);

cout<<endl;

break;

case 5:

cout<<"Postorder Traversal of BST:"<<endl;

bst.Postorder(root);

cout<<endl;

break;

case 6:

exit(1);

default:

cout<<"Wrong choice"<<endl;

}

}

}