#include <iostream>
using namespace std;
class Node {
public:
int data;
Node* leftNode;
Node* rightNode;
Node(int _data) {
data=_data;//Data
leftNode=NULL;
rightNode=NULL;
}
};
class BinarySearchTree {
public:
Node* root;
BinarySearchTree() {
root=NULL;
}
void insert(Node * _node) {
if (root==NULL) {
root= _node;
} else {
Node* tmp=root;
while (tmp!=NULL) {
if ((* _node).data>=(*tmp).data) {
if ((* tmp).rightNode==NULL) {
(*tmp).rightNode=_node;
break;
} else {
tmp=(*tmp).rightNode;
}
} else {
if ((* tmp).leftNode==NULL) {
(* tmp).leftNode=_node;
break;
} else {
tmp=(* tmp).leftNode;
}
}
}
}
}
void preOrderDisplay(Node * node) {
cout << (*node).data <<endl;
if ((*node).leftNode!=NULL) {
preOrderDisplay((*node).leftNode);
}
if ((*node).rightNode!=NULL) {
preOrderDisplay((*node).rightNode);
}
}
};
int main() {
Node* firstNode=new Node(1);
Node* secondNode=new Node(2);
Node* thirdNode=new Node(3);
Node* fourthNode=new Node(4);
BinarySearchTree bst;
bst.insert(fourthNode);
bst.insert(firstNode);
bst.insert(thirdNode);
bst.insert(secondNode);
bst.preOrderDisplay(bst.root);
return 0;
}