binarysearchtree_I.cpp

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

struct node {
	int key;
	node* left;
	node* right;
};

node *root = NULL;

// Insert new key
void insert(int key)
{
	node *n = new node();
	*n = { NULL };
	n->key = key;
	node *x = root;
	node *y;
	y = NULL;
	while (x != NULL) {
		y = x;
		if (x->key >= n->key)
			x = x->left;
		else
			x = x->right;
	}
	if (y == NULL)
		root = n;
	else if (y->key >= n->key)
		y->left = n;
	else
		y->right = n;
}

// Pre-order traversal
void preorder(node* n)
{
	cout << " " << n->key;
	if(n->left != NULL)
		preorder(n->left);
	if (n->right != NULL)
		preorder(n->right);
}

// In-order traversal
void inorder(node* n)
{
	if(n->left != NULL)
		inorder(n->left);
	cout << " " << n->key;
	if (n->right != NULL)
		inorder(n->right);
}

// MAIN FUNCTION
int main(int argc, char** argv)
{
	// input
	string opt;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> opt;
		if (opt == "insert") {
			// insert new node
			int key;
			cin >> key;
			insert(key);
		}
		if (opt == "print") {
			inorder(root);
			cout << endl;
			preorder(root);
			cout << endl;
		}

	}
	return 0;
}