Answer to Question #284613 in C++ for f0rGoTTen

Question

10, 20, 4, 5, 30, 1, 6, 3, 9, 60, 70, 90

Simulate the recursion for in-order and post order traversal of BST

Answer 1

#include<iostream>
#include<vector>

using namespace std;


struct Node
{
	int data;
	struct Node *right;
	struct Node *left;
	Node(int _data) :data(_data), left(NULL), right(NULL) {}
};


class BST
{
public:
	struct Node* BSTInsert(int value, Node* p)
	{
		if (p == NULL)
		{
			p = new Node(value);
		}
		else if (value<p->data)
		{
			p->left = BSTInsert(value, p->left);
		}
		else if (value>p->data)
		{
			p->right = BSTInsert(value, p->right);
		}
		return p;
	}


	void Postorder(struct Node *p)
	{
		if (p != NULL)
		{
			Postorder(p->left);
			Postorder(p->right);
			cout << p->data << " ";
		}
	}


	void Inorder(struct Node *p)
	{
		if (p != NULL)
		{
			Postorder(p->left);
			cout << p->data << " ";
			Postorder(p->right);
		}
	}
};

int main()
{
	BST bs;
	int num;
	Node *root = new Node(10);//10, 20, 4, 5, 30, 1, 6, 3, 9, 60, 70, 90


	bs.BSTInsert(20, root);
	bs.BSTInsert(4, root);
	bs.BSTInsert(5, root);
	bs.BSTInsert(30, root);
	bs.BSTInsert(1, root);
	bs.BSTInsert(6, root);
	bs.BSTInsert(3, root);
	bs.BSTInsert(9, root);
	bs.BSTInsert(60, root);
	bs.BSTInsert(70, root);
	bs.BSTInsert(90, root);


	cout << "\nInorder:";
	bs.Inorder(root);
	cout << "\nPostorder";
	bs.Postorder(root);
}