//============================================================================
// Name        : BinarySearchTree.cpp
// Author      : Ken
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <map>
using namespace std;

class Node{
public:
	int id;
	Node* p_parent;
	Node* p_left_child;
	Node* p_right_child;

	Node(): id(-1), p_parent(NULL), p_left_child(NULL), p_right_child(NULL){};
	Node(const int n):id(n), p_parent(NULL), p_left_child(NULL), p_right_child(NULL){}
};

class BinarySearchTree{
public:
	map<int, Node> node_map;
	int root_id;

	BinarySearchTree(): node_map(), root_id(){};


	void insert(int input){
		node_map[input] = Node(input); // THIS IS **PASS-BY-VALUE** !!!
		Node* y = NULL; //parent of x


		if(node_map.size()>=2){
		    Node* x = &node_map[root_id];
		    //cout << "x->id: " << x->id << "\n";

	    	while(x != NULL){
	    		y = x;

		    	if(node_map[input].id < x->id){
			    	x = x->p_left_child; // move to the left child
	    		}else{
		    		x = x->p_right_child; // move to the right child
		    	}
		    }
	    	//cout << "end of while loop\n";

	    	//if(x != NULL){
	    	//    cout << "x->id: " << x->id;}

	    	//if(y != NULL){
			//    cout << ", y->id: " << y->id;}

			//cout << ", z->id: " << node_map[z.id].id;

			//cout << "\n";

			node_map[input].p_parent = y;
		}

		if(y == NULL){ // T is empty
			root_id = node_map[input].id;
		}else if(input < y->id){
			y->p_left_child = &node_map[input];
		}else{
			y->p_right_child = &node_map[input];
		}
	}

	void printInorder(int node_id){
		Node& p_node = node_map[node_id];

		if(p_node.p_left_child != NULL){
			//cout << "print left branch\n";
		    printInorder(p_node.p_left_child->id);
		}

		cout << " " << node_id;

		if(p_node.p_right_child != NULL){
			//cout << "print right branch\n";
			printInorder(p_node.p_right_child->id);
		}
	}

	void printInorderTree(){
		printInorder(root_id);
	}

	void printPreorder(int node_id){
		Node& p_node = node_map[node_id];
		cout << " " << node_id;

		if(p_node.p_left_child != NULL){
		    printPreorder(p_node.p_left_child->id);
		}

		if(p_node.p_right_child != NULL){
			printPreorder(p_node.p_right_child->id);
		}
	}

	void printPreorderTree(){
		printPreorder(root_id);
	}

	void writeMap(){
		cout << "root id: " << root_id << ", root node: " << node_map[root_id].id << "\n";

		map<int, Node>::iterator p;
		for(p = node_map.begin(); p != node_map.end(); p++){
			cout << p->first << " " << p->second.id << "\n";
			Node& p_node = p->second;
			if(p_node.p_parent != NULL){
				cout << " parent: " << p_node.p_parent->id;
			}
			if(p_node.p_left_child != NULL){
				cout << " left_child: " << p_node.p_left_child->id;
			}
			if(p_node.p_right_child != NULL){
				cout << " right_child: " << p_node.p_right_child->id;
			}
			cout << "\n";
		}
	}
};


int main() {
	BinarySearchTree tree;

	int n, input;
	string command;
	cin >> n;

	for(int i=0; i<n; i++){
		cin >> command;
		if(command == "insert"){
			cin >> input;
			//cout << "insert(" << input << ")\n";
			tree.insert(input);
			//tree.writeMap();
			//cout << "\n\n\n";
		}
		if(command == "print"){
			//cout << "printInorderTree()\n";
			tree.printInorderTree();
			cout << "\n";
			//cout << "printPreorderTree()\n";
			tree.printPreorderTree();
			cout << "\n";
		}
	}
	//tree.writeMap();

	return 0;
}



Measured memory_bytes: 42100