README.md

Usage:

g++ -g tree.cpp # For random alloc
g++ -g tree.cpp -DUSE_ARENA # For continious

tree.cpp

#include <iostream>
#include <chrono>

struct Node {
    long long val;
    Node *left;
    Node *right;
};

#define NODE_SIZE sizeof(Node)
#define ARENA_SIZE 100000

class Memory {
    public:
        long long curr_count = 0;
        long long max_count = 0;
        Node arena[ARENA_SIZE];

        Memory() {
            curr_count = 0;
            max_count = ARENA_SIZE;
            // std::cout << "Created memory of count: " << ARENA_SIZE << ", size: " << ARENA_SIZE * NODE_SIZE << std::endl;
        }

        Node* get_next_node() {
            if (curr_count == max_count) {
                std::cerr << "Out of memory!" << std::endl;
                exit(1);
            }
            Node *new_node = (arena + curr_count++);
            return new_node;
        }

};

class Tree {
    private:
#ifdef USE_ARENA
        Memory m;
#endif
        Node *root;
        bool insert(long long key, Node* leaf);
        Node *new_node_api();
        void print_inorder(Node *node);

    public:
        Tree() {
            root = nullptr;
#ifdef USE_ARENA
            m = Memory();
#endif
        }

        ~Tree() {
            // tree_del();
        }

        bool insert(long long key);
        Node* find(long long key);
        void inorder();
};

Node* Tree::new_node_api() {
#ifdef USE_ARENA
    Node* node = m.get_next_node();
#else
    Node* node = new Node();
    int *tmp = new int[1000]; delete[] tmp; /* Ensure nodes are far apart*/
#endif

    return node;
}

bool Tree::insert(long long key) {
    if (root) {
        return insert(key, root);
    }

    root = new_node_api();
    root->val = key;
    root->left = nullptr;
    root->right = nullptr;

    return true;
}


bool Tree::insert(long long key, Node *leaf) {
    if (key < leaf->val) {
        if (leaf->left) {
            insert(key, leaf->left);
        } else {
            leaf->left = new_node_api();
            if (!leaf->left) {
                return false;
            }
            leaf->left->val = key;
            leaf->left->left = nullptr;
            leaf->left->right = nullptr;
        }
    } else {

        if (leaf->right) {
            insert(key, leaf->right);
        } else {
            leaf->right = new_node_api();
            if (!leaf->right) {
                return false;
            }
            leaf->right->val = key;
            leaf->right->left = nullptr;
            leaf->right->right = nullptr;
        }
    }

    return true;
}

void Tree::inorder() {
    print_inorder(root);
    std::cout << std::endl;
}

void Tree::print_inorder(Node *node) {
    if (!node) {
        return;
    }
    print_inorder(node->left);
    // std::cout << node->val << " " << std::endl;
    print_inorder(node->right);
}

int main() {
    long long node_count; std::cin >> node_count;
    Tree t = Tree();
    while(node_count--) {
        long long key; std::cin >> key;
        if (t.insert(key)) {
            // std::cout << "Inserted" << std::endl;
            continue;
        }
        // std::cout << "Insert Failed!" << std::endl;
    }
    auto start = std::chrono::high_resolution_clock::now();
    t.inorder();
    auto stop = std::chrono::high_resolution_clock::now(); 
    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(stop - start);
    std::cout << "Time: " << duration.count() << std::endl;
}