#include <iostream>
#include <vector>

using namespace std;

struct tree{
    tree* left;
    tree* right;
    int value;

    int size;
};

void add(int sValue, tree* root){
    if(root->size == 0){
        root->size++;
        root->value = sValue;
        return;
    }

    tree* var = new tree();
    var->value = sValue;

    int n = root->size+1;
    std::vector<bool> path;

    while(n > 1){
        path.push_back(n%2);
        n/=2;
    }

    tree* head = root;

    for(int i = path.size()-1; i >= 1; i--){
        if(path[i] == 0){
            head = head->left;
        }else{
            head = head->right;
        }
    }

    if(path[0] == 0){
            head->left = var;
    }else{
            head->right = var;
    }

    root->size++;
}

void display(tree* root, tree* head){
    if(root->size != 0){
        std::cout << "Rodzic[" << head->value << "]" << std::endl;

        if(head->left != NULL){
            std::cout << "L[" << head->left->value << "]" << std::endl;
        }

        if(head->right != NULL){
            std::cout << "R[" << head->right->value << "]" << std::endl;
        }

        if(head->left != NULL){
            display(root, head->left);
        }

        if(head->right != NULL){
            display(root, head->right);
        }
    }
}

void show(tree* root){
    display(root, root);
}

int main(){
    tree* drzewo = new tree();
    drzewo->left = NULL;
    drzewo->right = NULL;
    drzewo->size = 0;

    add(7, drzewo);
    add(5, drzewo);
    add(9, drzewo);
    add(2, drzewo);
    add(4, drzewo);
    add(6, drzewo);
    add(1, drzewo);

    show(drzewo);

    return 0;
}