path: root/bst.cc

#include <cstddef>
#include <iostream>
#include <memory>
#include <optional>

template <typename T> class bst {
public:
  using size_type = std::size_t;

private:
  T _key;
  std::optional<std::shared_ptr<bst>> _left;
  std::optional<std::shared_ptr<bst>> _right;

public:
  bst(T key) : _key(key) {}

  auto key() -> T { return this->_key; }
  auto key(T key) -> void { this->_key = key; }

  auto left() -> std::optional<T> { return this->_left; }
  auto left(T left) -> void { this->_left = left; }

  auto right() -> std::optional<T> { return this->_right; }
  auto right(T right) -> void { this->_right = right; }

  auto insert(T key) -> void {
    // A BST is structured in a way that values larger than the root node sit
    // right of the node, while values smaller sit left of it.
    //
    // If the key is greater than than this node's key, it will sit to the right
    // of it.
    if (key > this->_key) {
      // If this node already has a right value, we must tack it onto the end of
      // that node ...
      if (this->_right.has_value()) {
        std::cout << "inserting as right: " << key << "\n";

        // or keep trying until an empty branch is found.
        this->_right.value()->insert(key);
      } else {
        // If this branch was hit, that must mean that an empty right branch was
        // found, so we set it.
        this->_right = std::make_shared<bst<T>>(bst(key));

        std::cout << "set as right: " << key << "\n";
      }
    } else {
      // This is the same operation is above, but for values smaller than the
      // current BST node.
      if (this->_left.has_value()) {
        std::cout << "inserting as left: " << key << "\n";

        this->_left.value()->insert(key);
      } else {
        this->_left = std::make_shared<bst<T>>(bst(key));

        std::cout << "set as left: " << key << "\n";
      }
    }
  }

  auto size() -> bst::size_type {
    return
        // If the left value of the current node has a value, add one to
        // the accumulator (the +1 below), and continue down the branch
        (this->_left.has_value() ? this->_left.value()->size() : 0) +
        // The same as above, but for the right branch
        (this->_right.has_value() ? this->_right.value()->size() : 0) +
        // Additionally account for the root node itself
        1;
  }

  auto depth() -> bst::size_type {
    // Account for the root node, but also serve as the accumulator for the
    // below `depth` calls, similar as to the above `size` function
    return 1 +
           std::max(this->_left.has_value() ? this->_left.value()->depth() : 0,
                    this->_right.has_value() ? this->_right.value()->depth()
                                             : 0);
  }

  auto minimum() -> T {
    // Start with the root key as the base minimum, since the left branch may be
    // empty
    T minimum = this->_key;

    // If the left branch has a value, and the value is smaller than the root
    // node, consider it as a minimum
    if (this->_left.has_value() && this->_key > this->_left.value()->key()) {
      // Attempt to obtain the valid left branch value's left branch, otherwise,
      // minimum will return the top-level minimum of the left branch
      minimum = this->_left.value()->minimum();
    }

    return minimum;
  }

  auto maximum() -> T {
    // Identical to the `minimum` implementation, but considers the right-hand
    // branch
    T maximum = this->_key;

    if (this->_right.has_value() && this->_key < this->_right.value()->key()) {
      maximum = this->_right.value()->maximum();
    }

    return maximum;
  }

  static auto remove(std::optional<std::shared_ptr<bst>> bst,
                     T key) -> std::optional<std::shared_ptr<class bst>> {
    // If the current BST being evaluated has no value, it could not possibly be
    // considering for child removal
    if (!bst.has_value()) {
      return std::nullopt;
    }

    // If the current BST's key is smaller than the target key, it must be on
    // the right-hand side, this additionally means that it is not the target
    // value
    if (bst.value()->_key < key) {
      bst.value()->_right = bst::remove(bst.value()->_right, key);

      return bst;
    } else if (bst.value()->_key > key) {
      bst.value()->_left = bst::remove(bst.value()->_left, key);

      return bst;
    }

    // At this point, the BST value has been found if available through a series
    // of greater than, less than evaluations

    if (!bst.value()->_left.has_value()) {
      auto temporary_bst = bst.value()->_right;

      bst.value().reset();

      return temporary_bst;
    } else if (!bst.value()->_right.has_value()) {
      auto temporary_bst = bst.value()->_left;

      bst.value().reset();

      return temporary_bst;
    }

    auto next_parent = bst.value()->_right;
    auto next = bst.value()->_right;

    while (next.value()->_left.has_value()) {
      next_parent = next;
      next = next.value()->_left;
    }

    next_parent.value()->_left = next.value()->_right;
    bst.value()->_key = next.value()->_key;

    next.value().reset();

    return bst;
  }

  auto remove(T key) -> void {
    // `remove` is easier with recursion, so its wrapped
    this->remove(std::make_shared<bst<T>>(*this), key);
  }

  static auto print_from_largest_to_smallest(
      std::optional<std::shared_ptr<bst>> bst) -> void {
    if (bst.has_value()) {
      print_from_largest_to_smallest(bst.value()->_right);

      std::cout << bst.value()->_key << ' ';

      print_from_largest_to_smallest(bst.value()->_left);
    }
  }

  auto print_from_largest_to_smallest() -> void {
    print_from_largest_to_smallest(std::make_shared<bst<T>>(*this));

    std::cout << '\n';
  }

  static auto print_from_smallest_to_largest(
      std::optional<std::shared_ptr<bst>> bst) -> void {
    if (bst.has_value()) {
      print_from_smallest_to_largest(bst.value()->_left);

      std::cout << bst.value()->_key << ' ';

      print_from_smallest_to_largest(bst.value()->_right);
    }
  }

  auto print_from_smallest_to_largest() -> void {
    print_from_smallest_to_largest(std::make_shared<bst<T>>(*this));

    std::cout << '\n';
  }

  static auto invert(std::optional<std::shared_ptr<bst>> bst)
      -> std::optional<std::shared_ptr<class bst>> {
    if (bst.has_value()) {
      if (bst.value()->_left.has_value() || bst.value()->_right.has_value()) {
        auto left = invert(bst.value()->_left);
        auto right = invert(bst.value()->_right);

        bst.value()->_left = right;
        bst.value()->_right = left;
      }

      return bst;
    }

    return std::nullopt;
  }

  auto invert() -> void { invert(std::make_shared<bst<T>>(*this)); }
};

auto main() -> int {
  bst<int> bst(2);

  bst.insert(3);
  bst.insert(4);
  bst.insert(5);
  bst.insert(1);

  std::cout << "print largest to smallest: ";

  bst.print_from_largest_to_smallest();

  std::cout << "print smallest to largest: ";

  bst.print_from_smallest_to_largest();

  std::cout << "size: " << bst.size() << '\n';
  std::cout << "depth: " << bst.depth() << '\n';
  std::cout << "minimum: " << bst.minimum() << '\n';
  std::cout << "maximum: " << bst.maximum() << '\n';

  bst.remove(5);

  std::cout << "size: " << bst.size() << '\n';

  std::cout << "inverted: ";

  bst.invert();
  bst.invert();
  bst.print_from_largest_to_smallest();

  return 0;
}