#include <iostream>

using namespace std;

struct Node
{
    Node* parent;
    Node* left;
    Node* right;
    int value;
};

class BST
{
    Node* root;

public:
    BST() { root = nullptr; };
    ~BST() { delete root; };
    void push(int a);
    void place(int a, Node* n);
    //void pop();
    //void print();
    void search();
    void preorder(Node* n);
    void inorder(Node* n);
    void postorder(Node* n);
    void check(Node* n);
};

int main()
{
    BST b;

    b.push(5);
    b.push(9);
    b.push(2);
    b.push(4);
    b.push(1);
    b.push(7);

    b.search();
    return 0;
}



void BST::push(int a)
{
    Node* new_node = new Node;
    new_node->value = a;

    if (!root)
    {
        new_node->parent = nullptr;
        root = new_node;
        new_node->left = nullptr;
        new_node->right = nullptr;
    }
    else
    {
        place(a, root);
    }
}

void BST::place(int a, Node* n)
{
    if (a < n->value)
    {
        if (n->left)
            place(a, n->left);
        else
        {
            Node* new_node = new Node;
            new_node->value = a;
            n->left = new_node;
            new_node->left = nullptr;
            new_node->right = nullptr;
        }
    }
    else
    {
        if (n->right)
            place(a, n->right);
        else
        {
            Node* new_node = new Node;
            new_node->value = a;
            n->right = new_node;
            new_node->left = nullptr;
            new_node->right = nullptr;
        }
    }
}

void BST::search()
{
    //cout << "pre-order: " << endl;
    //preorder(root);
    cout << "in-order: " << endl;
    inorder(root);
    //cout << "post-order: " << endl;
    //postorder(root);

    //cout << "check: " << endl;
    //check(root);

}

void BST::preorder(Node* n)
{
    cout << n->value << endl;
    if (n->left)
        preorder(n->left);
    if (n->right)
        preorder(n->right);
}

void BST::inorder(Node * n)
{
    if (n->left)
        preorder(n->left);
    cout << n->value << endl;
    if (n->right)
        preorder(n->right);
}

void BST::postorder(Node * n)
{
    if (n->left)
        preorder(n->left);
    if (n->right)
        preorder(n->right);
    cout << n->value << endl;
}

void BST::check(Node* n)
{
    cout << "parent: " << n->parent << endl;
    cout << "value: " << n->value << endl;
    cout << "node: " << n << endl;
    cout << "l: " << n->left << endl;
    cout << "r: " << n->right << endl;
    cout << "---------------------\n\n";
    if (n->left)
        check(n->left);
    if (n->right)
        check(n->right);
}