// Árbol binario de búsqueda sin ningún balance, para comparar. Solo inserta y mide.
// Es el BstSet de la semana 10, reducido a lo que usan las mediciones.
#ifndef PLAIN_TREE_H
#define PLAIN_TREE_H

#include <cstddef>
#include <utility>
#include <vector>

template <typename K>
class PlainTree {
    struct Node {
        K key;
        Node* left = nullptr;
        Node* right = nullptr;
    };

public:
    PlainTree() = default;

    // Sin recursión: un árbol sin balance puede ser una cadena.
    ~PlainTree() {
        std::vector<Node*> pending;
        if (root_ != nullptr) {
            pending.push_back(root_);
        }
        while (!pending.empty()) {
            Node* node = pending.back();
            pending.pop_back();
            if (node->left != nullptr) {
                pending.push_back(node->left);
            }
            if (node->right != nullptr) {
                pending.push_back(node->right);
            }
            delete node;
        }
    }

    PlainTree(const PlainTree&) = delete;
    PlainTree& operator=(const PlainTree&) = delete;

    bool insert(const K& key) {
        Node** link = &root_;
        while (*link != nullptr) {
            if (key < (*link)->key) {
                link = &(*link)->left;
            } else if ((*link)->key < key) {
                link = &(*link)->right;
            } else {
                return false;
            }
        }
        *link = new Node{key};
        size_++;
        return true;
    }

    bool contains(const K& key) const {
        const Node* node = root_;
        while (node != nullptr) {
            if (key < node->key) {
                node = node->left;
            } else if (node->key < key) {
                node = node->right;
            } else {
                return true;
            }
        }
        return false;
    }

    std::size_t size() const { return size_; }

    // Altura nivel por nivel, y la suma de las profundidades de todos los nodos: sin recursión.
    std::pair<int, long> height_and_depth() const {
        int levels = 0;
        long depth_sum = 0;
        std::vector<const Node*> level;
        if (root_ != nullptr) {
            level.push_back(root_);
        }
        while (!level.empty()) {
            depth_sum += levels * static_cast<long>(level.size());
            std::vector<const Node*> next;
            for (const Node* node : level) {
                if (node->left != nullptr) {
                    next.push_back(node->left);
                }
                if (node->right != nullptr) {
                    next.push_back(node->right);
                }
            }
            level = std::move(next);
            levels++;
        }
        return {levels - 1, depth_sum};
    }

    int height() const { return height_and_depth().first; }

private:
    Node* root_ = nullptr;
    std::size_t size_ = 0;
};

#endif