Given binary tree with n nodes, perform following operations on it: Perform preorder and post order traversal • Create a mirror image of it • Find the height of tree • Copy this tree to another [operator=] • Count number of leaves, number of internal nodes. Erase all nodes in a binary tree. (implement both recursive and non-recursive methods)

	#include<iostream>
	#include<string>
	const int MAX=30;
	using namespace std;
	class Node {
	char data;
	Node* left;
	Node* right;
	public:
	Node() {
	data=0;
	left=right=NULL;
	}
	Node(char data) {
	this->data=data;
	left=right=NULL;
	}
	friend class Tree;
	};
	class stack {
	Node* item[MAX];
	int top;
	public:
	stack() {
	top=-1;
	}
	void push(Node* node) {
	if(isFull()) {
	cout<<"Stack is full"<<endl;
	}
	else {
	top++;
	item[top]=node;
	}
	}
	Node* topData() {
	return item[top];
	}
	Node* pop() {
	if(isEmpty()) {
	cout<<"Stack is empty"<<endl;
	}
	else
	return item[top--];
	}
	int size() {
	return top+1;
	}
	int isEmpty() {
	if(top==-1)
	return 1;
	return 0;
	}
	int isFull() {
	if(top==MAX-1)
	return 1;
	return 0;
	}
	friend class Tree;
	};
	class Tree {
	Node* root;
	public:
	Tree() {
	root=NULL;
	}
	Node* getRoot() {
	return root;
	}
	void setRoot(Node* node) {
	root=node;
	}
	Node* newNode() {
	Node* temp;
	char ch;
	cout<<"Enter Data: ";
	cin>>ch;
	temp=new Node(ch);
	return temp;
	}
	void createTree(Node* node) {
	bool decision;
	if(root==NULL)
	root=node;
	Node* temp=node;
	cout<<"Do you want to set left child of node <<"<<temp->data<<">> (0/1): ";
	cin>>decision;
	if(decision==1) {
	temp->left=newNode();
	createTree(temp->left);
	}
	cout<<"Do you want to set right child of node< <"<<temp->data<<">> (0/1): ";
	cin>>decision;
	if(decision==1) {
	temp->right=newNode();
	createTree(temp->right);
	}
	}
	int height(Node* node) {
	if(node==NULL) return 0;
	int left=height(node->left);
	int right=height(node->right);
	if(left > right)
	return left+1;
	else
	return right+1;
	}
	int heightNonR(Node* node) {
	stack s;
	s.push(root);
	int maxDepth = 0;
	Node *prev = NULL;
	while (!s.isEmpty()) {
	Node *curr = s.topData();
	if (!prev || prev->left == curr || prev->right == curr) {
	if (curr->left)
	s.push(curr->left);
	else if (curr->right)
	s.push(curr->right);
	} else if (curr->left == prev) {
	if (curr->right)
	s.push(curr->right);
	} else {
	s.pop();
	}
	prev = curr;
	if (s.size() > maxDepth)
	maxDepth = s.size();
	}
	return maxDepth;
	}
	void preorderRecursive(Node* node) {
	if(node==NULL) return;
	cout<<node->data<<" ";
	preorderRecursive(node->left);
	preorderRecursive(node->right);
	}
	void postorderRecursive(Node* node) {
	if(node==NULL) return;
	postorderRecursive(node->left);
	postorderRecursive(node->right);
	cout<<node->data<<" ";
	}
	void inorderRecursive(Node* node) {
	if(node==NULL) return;
	inorderRecursive(node->left);
	cout<<node->data<<" ";
	inorderRecursive(node->right);
	}
	void preorderNonRecursive(Node* node) {
	if(node==NULL) return;
	stack s1;
	Node* temp=node;
	s1.push(temp);
	while(!s1.isEmpty() && s1.topData() != NULL) {
	temp=s1.pop();
	cout<<temp->data<<" ";
	if(temp->right)
	s1.push(temp->right);
	if(temp->left)
	s1.push(temp->left);
	}
	}
	void inorderNonRecursive(Node* node) {
	if(node==NULL) return;
	stack s1;
	Node* temp=node;
	while(temp!=NULL || !s1.isEmpty()) {
	while(temp!= NULL) {
	s1.push(temp);
	temp=temp->left;
	}
	temp=s1.pop();
	cout<<temp->data<<" ";
	temp=temp->right;
	}
	}
	void postorderNonRecursive(Node* node) {
	if(node==NULL) return;
	stack s;
	Node *root=node;
	do {
	while(root != NULL) {
	if(root->right!=NULL)
	s.push(root->right);
	s.push(root);
	root=root->left;
	}
	root=s.pop();
	if(root->right && s.topData()==root->right) {
	s.pop();
	s.push(root);
	root=root->right;
	}
	else {
	cout<<root->data<<" ";
	root=NULL;
	}
	}
	while(!s.isEmpty());
	root=NULL;
	}
	int getLeafCount(Node* node) {
	if(node==NULL)
	return 0;
	else if(node->left== NULL && node->right==NULL)
	return 1;
	return getLeafCount(node->left)+getLeafCount(node->right);
	}
	int getLeafCountNonR(Node* node) {
	int count=0;
	stack s;
	Node* temp;
	s.push(node);
	while(!s.isEmpty()) {
	temp=s.pop();
	if(temp->left==NULL && temp->right==NULL) {
	count++;
	}
	if(temp->left != NULL)
	s.push(temp->left);
	if(temp->right != NULL)
	s.push(temp->right);
	}
	return count;
	}
	int getInternalCountNonR(Node* node) {
	int count=0;
	stack s;
	Node* temp;
	s.push(node);
	while(!s.isEmpty()) {
	temp=s.pop();
	if(temp->left!=NULL || temp->right!=NULL) {
	count++;
	}
	if(temp->left != NULL)
	s.push(temp->left);
	if(temp->right != NULL)
	s.push(temp->right);
	}
	return count;
	}
	void eraseNodes(Node* node) {
	stack s;
	Node *temp=node;
	do {
	while(temp != NULL) {
	if(temp->right!=NULL)
	s.push(temp->right);
	s.push(temp);
	temp=temp->left;
	}
	temp=s.pop();
	if(temp->right && s.topData()==temp->right) {
	s.pop();
	s.push(temp);
	temp=temp->right;
	}
	else {
	temp->left=NULL;
	temp->right=NULL;
	delete temp;
	temp=NULL;
	}
	}
	while(!s.isEmpty());
	root=NULL;
	}
	void eraseNodesR(Node* node) {
	if(node != NULL) {
	eraseNodesR(node->left);
	eraseNodesR(node->right);
	delete node;
	}
	root=NULL;
	}
	int getInternalNodeCount(Node* node) {
	if(node==NULL || (node->left== NULL && node->right ==NULL))
	return 0;
	return getInternalNodeCount(node->left)+1+getInternalNodeCount(node->right);
	}
	void mirrorTree(Node* node) {
	if(node==NULL)
	return;
	else {
	mirrorTree(node->left);
	mirrorTree(node->right);
	Node* temp=node->left;
	node->left=node->right;
	node->right=temp;
	}
	}
	void mirrorTreeR(Node* node) {
	Node* temp;
	Node* temp1;
	stack s;
	s.push(node);
	while(!s.isEmpty()) {
	temp=s.pop();
	if(temp->left!=NULL)
	s.push(temp->left);
	if(temp->right!=NULL)
	s.push(temp->right);
	temp1=temp->left;
	temp->left=temp->right;
	temp->right=temp1;
	}
	}
	// void operator=(Tree &t) {
	// Node* temp=t.getRoot();
	// Node* res=new Node(temp->data);
	// this->root=res;
	// if(temp->left==NULL)
	// res->left=NULL;
	// else
	// res->left=temp->left;
	//
	// if(temp->right==NULL)
	// res->right=NULL;
	// else
	// res->right=temp->right;
	// }
	void operator=(Tree &t) {
	Node* node=t.getRoot();
	if(node==NULL) return;
	stack s1,s2,s3;
	Node* temp;
	s1.push(node);
	while(!s1.isEmpty() && s1.topData() != NULL) {
	temp=s1.pop();
	Node* temp1=new Node(temp->data);
	if(s2.topData() != NULL) {
	if(s3.topData()!= NULL && s3.topData()->left && s2.topData()->left == NULL) {
	if(s3.topData()->right == NULL) {
	//if no right child pop parent from s2
	s2.topData()->left=temp1;
	s3.pop();
	if(s2.size() > 1)
	s2.pop();
	}
	else {
	s2.topData()->left=temp1;
	}
	}
	else {
	s2.topData()->right=temp1;
	if(s2.size() > 1)
	s2.pop();
	}
	}
	if(temp->left != NULL || temp->right != NULL) {
	s2.push(temp1);
	s3.push(temp);
	}
	if(temp->right)
	s1.push(temp->right);
	if(temp->left)
	s1.push(temp->left);
	}
	this->setRoot(s2.pop());
	}
	};
	int main() {
	Tree t,t2;
	char ch;
	int choice;
	Node* temp;
	Node* temp1;
	temp=t.newNode();
	t.createTree(temp);
	do {
	cout<<"1. For height recursive\n";
	cout<<"2. For height Non recursive \n";
	cout<<"3. For Preorder Recursive \n";
	cout<<"4. For Postorder Recursive \n";
	cout<<"5. For Inorder Recursive \n";
	cout<<"6. For Preorder Non-Recursive \n";
	cout<<"7. For Postorder Non-Recursive \n";
	cout<<"8. For Inorder Non-Recursive \n";
	cout<<"9. For mirroring Recursive\n";
	cout<<"10. Fot mirroring Non recursive \n";
	cout<<"11. For counting leaf nodes recursive \n";
	cout<<"12. For counting leaf nodes Non recursive \n";
	cout<<"13. For counting internal nodes recursive \n";
	cout<<"14. For counting interna nodes Non recursive \n";
	cout<<"15. For deleting nodes Non recursive \n";
	cout<<"16. For deleting nodes recursive \n";
	cout<<"17. For copying tree \n";
	cout<<"Enter your choice: ";
	cin>>choice;
	switch(choice) {
	case 1: cout<<"Height is: "<<t.height(t.getRoot())<<endl;
	break;
	case 2: cout<<"Height is: "<<t.heightNonR(t.getRoot())<<endl;
	break;
	case 3: cout<<"Preorder Recursive: ";
	t.preorderRecursive(t.getRoot());
	cout<<endl;
	break;
	case 4: cout<<"Postorder Recursive: ";
	t.postorderRecursive(t.getRoot());
	cout<<endl;
	break;
	case 5: cout<<"Inorder Recursive: ";
	t.inorderRecursive(t.getRoot());
	cout<<endl;
	break;
	case 6: cout<<"Preorder Non Recursive: ";
	t.preorderNonRecursive(t.getRoot());
	cout<<endl;
	break;
	case 7: cout<<"Postorder Non Recursive: ";
	t.postorderNonRecursive(t.getRoot());
	cout<<endl;
	break;
	case 8: cout<<"Inorder Non Recursive: ";
	t.inorderNonRecursive(t.getRoot());
	cout<<endl;
	break;
	case 9: t.mirrorTree(t.getRoot());
	break;
	case 10:t.mirrorTreeR(t.getRoot());
	break;
	case 11:cout<<t.getLeafCount(t.getRoot())<<endl;
	break;
	case 12:cout<<t.getLeafCountNonR(t.getRoot())<<endl;
	break;
	case 13:cout<<t.getInternalNodeCount(t.getRoot())<<endl;
	break;
	case 14:cout<<t.getInternalCountNonR(t.getRoot())<<endl;
	break;
	case 15:t.eraseNodes(t.getRoot());
	cout<<"Nodes Deleted..."<<endl;
	break;
	case 16:t.eraseNodesR(t.getRoot());
	cout<<"Nodes Deleted..."<<endl;
	break;
	case 17:t2=t;
	cout<<"Tree copied..."<<endl;
	cout<<"Inorder Recursive is: ";
	t2.inorderRecursive(t2.getRoot());
	cout<<endl;
	break;
	}
	cout<<"Do you want to continue (Y/N): ";
	cin>>ch;
	}while(ch=='y'|| ch=='Y');
	return 0;
	}

view raw BinaryTree.cpp hosted with ❤ by GitHub