Write C++ program to create a Binary Search Tree from the data given below.
Problem Statement:
Write C++ program to create a Binary Search Tree from the data given below.
Values = {11,6,15,4,8,13,19,16}
Perform the post-order, preorder and inorder traversals on the BST constructed using above data. You will store these traversals in three different stacks using the push() method of stack. After that you will print these traversals in reverse order using the pop() method of stack.
You are required to develop a C++ program implementing Binary Search Tree (BST) and Stack data structure for the above scenario. Your program must meet the following requirements:
1. Construct Binary Search Tree, based upon above given data.
2. Perform the In-order, pre-order, post-order traversals on BST.
3. Store the In-order, pre-order, post-order traversals in three different stacks using a single Stack class. (You will create only a single Stack class in your code. Using more than one Stack class is not allowed).
4. Stack should be implemented using linked list.
5. Print all three traversals in reverse order using pop() method of stack
Details:
Your solution must contain the following:
1. Node Class (for creating nodes of Stack)
2. Stack Class (for storing the traversals of BST. Same stack class will be used for making three different stacks)
3. TreeNode template Class (to create the BST given above. The class should contain the constructors, necessary getter and setters, insert() method for inserting the nodes in tree,3 traversal methods inOrder(), preOrder(), postOrder()
4. Main() method.
Solution:
Program:
#include <iostream>
#include <stack>
using namespace std;
template <typename T>
class TreeNode {
public:
T data;
TreeNode<T>* left;
TreeNode<T>* right;
TreeNode(T data) {
this->data = data;
left = NULL;
right = NULL;
}
void insert(T data) {
if (data < this->data) {
if (left == NULL) {
left = new TreeNode<T>(data);
} else {
left->insert(data);
}
} else {
if (right == NULL) {
right = new TreeNode<T>(data);
} else {
right->insert(data);
}
}
}
void inOrder(stack<T> &s) {
if (left != NULL) {
left->inOrder(s);
}
s.push(data);
if (right != NULL) {
right->inOrder(s);
}
}
void preOrder(stack<T> &s) {
s.push(data);
if (left != NULL) {
left->preOrder(s);
}
if (right != NULL) {
right->preOrder(s);
}
}
void postOrder(stack<T> &s) {
if (left != NULL) {
left->postOrder(s);
}
if (right != NULL) {
right->postOrder(s);
}
s.push(data);
}
};
int main() {
stack<int> s;
TreeNode<int>* root = new TreeNode<int>(11);
root->insert(6);
root->insert(15);
root->insert(4);
root->insert(8);
root->insert(13);
root->insert(19);
root->insert(16);
cout << "Reverse Order of In-Order Travsersal" << endl;
root->inOrder(s);
while (!s.empty()) {
cout << s.top() << endl;
s.pop();
}
cout << "Reverse Order of Pre-Order Travsersal" << endl;
root->preOrder(s);
while (!s.empty()) {
cout << s.top() << endl;
s.pop();
}
cout << "Reverse Order of Post-Order Travsersal" << endl;
root->postOrder(s);
while (!s.empty()) {
cout << s.top() << endl;
s.pop();
}
return 0;
}
Output:
No comments