A simple C++ tree implementation

Tree.h

/*
  Copyright 2023 Abdul Rahman Dabbour

  Permission is hereby granted, free of charge, to any person obtaining a copy
  of this software and associated documentation files (the "Software"), to deal
  in the Software without restriction, including without limitation the rights
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the Software is
  furnished to do so, subject to the following conditions:

  The above copyright notice and this permission notice shall be included in
  all copies or substantial portions of the Software.

  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  SOFTWARE.
*/

/*
  This is a very simple implementation of a tree, with zero guarantees, done for
  educational purposes only. The code is not commented because it is quite
  simple, and under the implementation is a googletest suite of
  not-so-comprehensive tests that can be used if you want to continue
  development.
*/

#include <cstddef>
#include <iostream>
#include <memory>
#include <stdexcept>
#include <vector>

template <typename T = int>
class Vertex;
template <typename T = int>
using VertexPtr = std::shared_ptr<Vertex<T>>;
template <typename T = int>
using VertexPtrVec = std::vector<std::shared_ptr<Vertex<T>>>;

template <typename T>
class Vertex {
 public:
  explicit Vertex(T val) { data = val; }
  void addChild(VertexPtr<T> child) { children.push_back(child); }
  void removeChild(VertexPtr<T> child) {
    children.erase(std::remove(children.begin(), children.end(), child),
                   children.end());
  }
  auto getData() const -> T { return data; }
  auto getChildren() -> VertexPtrVec<T> & { return children; }
  auto isLeaf() const -> bool { return children.empty(); }

 private:
  int data;
  VertexPtrVec<T> children;
};

template <typename T = int>
class Tree {
 public:
  Tree() : root(nullptr){};
  explicit Tree(VertexPtr<T> root_vertex) : root(root_vertex) {}
  explicit Tree(T root_value) : root(std::make_shared<Vertex>(root_value)) {}

  void setRoot(VertexPtr<T> new_root) { root = new_root; }

  void insert(VertexPtr<T> parent, VertexPtr<T> child) {
    if (parent == nullptr || child == nullptr || root == nullptr) {
      throw std::runtime_error("parent or child or root is a nullptr");
    }
    parent->addChild(child);
  }

  void remove(VertexPtr<T> vertex) {
    if (root == nullptr || vertex == nullptr) return;
    if (root == vertex) {
      root = nullptr;
      return;
    }
    removeHelper(root, vertex);
  }

  auto search(T vertex_value) -> VertexPtrVec<T> {
    VertexPtrVec<T> result;
    searchHelper(root, vertex_value, result);
    return result;
  }

  auto size() const -> size_t { return sizeHelper(root); }

  auto isEmpty() const -> bool { return root == nullptr; }

  auto getRoot() const -> VertexPtr<T> { return root; }

  auto getHeight() const -> size_t {
    if (root == nullptr) return 0;
    return getHeightHelper(root);
  }

  auto getDepth(VertexPtr<T> vertex) const -> size_t {
    return getDepthHelper(root, vertex, 0);
  }

  auto getChildren(VertexPtr<T> vertex) const -> VertexPtrVec<T> & {
    return vertex->getChildren();
  }

  auto getParent(VertexPtr<T> vertex) const -> VertexPtr<T> {
    return getParentHelper(root, vertex);
  }

  auto isLeaf(VertexPtr<T> vertex) const -> bool { return vertex->isLeaf(); }

  auto isRoot(VertexPtr<T> vertex) const -> bool {
    if (vertex == nullptr) {
      throw std::runtime_error("quered vertex is a nullptr!");
    }
    if (root == nullptr) {
      throw std::runtime_error("tree root is a nullptr!");
    }
    return vertex == root;
  }

  void clear() {
    clearHelper(root);
    root = nullptr;
  }

 private:
  VertexPtr<T> root;

  auto getDepthHelper(VertexPtr<T> current, VertexPtr<T> vertex,
                      size_t depth) const -> size_t {
    if (current == nullptr) return 0;
    if (current == vertex) return depth;
    for (const auto &child : current->getChildren()) {
      const auto childDepth = getDepthHelper(child, vertex, depth + 1);
      if (childDepth != 0) return childDepth;
    }
    return 0;
  }

  auto sizeHelper(VertexPtr<T> vertex) const -> size_t {
    if (vertex == nullptr) return 0;
    size_t count = 1;
    for (const auto &child : vertex->getChildren()) count += sizeHelper(child);
    return count;
  }

  void removeHelper(VertexPtr<T> current, VertexPtr<T> vertex) {
    auto &children = current->getChildren();

    for (auto it = children.begin(); it != children.end();) {
      if (*it == vertex) {
        it = children.erase(it);
        return;
      } else {
        removeHelper(*it, vertex);
        ++it;
      }
    }
  }

  auto getHeightHelper(VertexPtr<T> vertex) const -> size_t {
    if (vertex == nullptr) return 0;
    size_t maxHeight = 0;
    for (const auto &child : vertex->getChildren()) {
      maxHeight = std::max(maxHeight, getHeightHelper(child));
    }
    return maxHeight + 1;
  }

  auto getParentHelper(VertexPtr<T> current, VertexPtr<T> vertex) const
      -> VertexPtr<T> {
    if (current == nullptr || current == vertex) return nullptr;
    for (const auto &child : current->getChildren()) {
      if (child == vertex) return current;
      auto parent = getParentHelper(child, vertex);
      if (parent != nullptr) return parent;
    }
    return nullptr;
  }

  void clearHelper(VertexPtr<T> vertex) {
    if (vertex == nullptr) return;
    for (const auto &child : vertex->getChildren()) clearHelper(child);
    vertex->getChildren().clear();
  }

  void searchHelper(VertexPtr<T> vertex, int target,
                    VertexPtrVec<T> &result) const {
    if (vertex == nullptr) return;
    if (vertex->getData() == target) result.push_back(vertex);
    for (const auto &c : vertex->getChildren()) searchHelper(c, target, result);
  }
};

/*
#include "gtest/gtest.h"

TEST(TreeTest, InsertAndRemove) {
  auto root = std::make_shared<Vertex<int>>(1);
  Tree tree{root};
  auto child1 = std::make_shared<Vertex<int>>(2);
  auto child2 = std::make_shared<Vertex<int>>(3);
  auto grandchild = std::make_shared<Vertex<int>>(4);

  tree.insert(root, child1);
  tree.insert(root, child2);
  tree.insert(child1, grandchild);

  EXPECT_EQ(tree.size(), 4);

  EXPECT_EQ(tree.getRoot(), root);
  EXPECT_EQ(tree.getChildren(root).size(), 2);
  EXPECT_EQ(tree.getChildren(child1).size(), 1);
  EXPECT_EQ(tree.getParent(child1), root);

  tree.remove(child1);
  tree.remove(child2);

  EXPECT_EQ(tree.size(), 1);

  EXPECT_EQ(tree.getChildren(root).size(), 0);
  EXPECT_EQ(tree.getParent(root), nullptr);
}

TEST(TreeTest, Search) {
  auto root = std::make_shared<Vertex<int>>(1);
  Tree tree{root};
  auto child1 = std::make_shared<Vertex<int>>(2);
  auto child2 = std::make_shared<Vertex<int>>(3);
  auto grandchild = std::make_shared<Vertex<int>>(2);

  tree.insert(root, child1);
  tree.insert(root, child2);
  tree.insert(child1, grandchild);

  auto result1 = tree.search(2);
  auto result2 = tree.search(3);

  EXPECT_EQ(result1.size(), 2);
  EXPECT_EQ(result2.size(), 1);
  EXPECT_EQ(result1[0], child1);
  EXPECT_EQ(result1[1], grandchild);
  EXPECT_EQ(result2[0], child2);
}

TEST(TreeTest, Height) {
  auto root = std::make_shared<Vertex<int>>(1);
  Tree tree{root};
  auto child1 = std::make_shared<Vertex<int>>(2);
  auto child2 = std::make_shared<Vertex<int>>(3);
  auto grandchild1 = std::make_shared<Vertex<int>>(4);
  auto grandchild2 = std::make_shared<Vertex<int>>(5);
  auto grandchild3 = std::make_shared<Vertex<int>>(6);

  tree.insert(root, child1);
  tree.insert(root, child2);
  tree.insert(child1, grandchild1);
  tree.insert(child1, grandchild2);
  tree.insert(child2, grandchild3);

  EXPECT_EQ(tree.getHeight(), 3);
}

TEST(TreeTest, Depth) {
  auto root = std::make_shared<Vertex<int>>(1);
  Tree tree{root};
  auto child1 = std::make_shared<Vertex<int>>(2);
  auto child2 = std::make_shared<Vertex<int>>(3);
  auto grandchild1 = std::make_shared<Vertex<int>>(4);
  auto grandchild2 = std::make_shared<Vertex<int>>(5);

  tree.insert(root, child1);
  tree.insert(root, child2);
  tree.insert(child1, grandchild1);
  tree.insert(child2, grandchild2);

  EXPECT_EQ(tree.getDepth(root), 0);
  EXPECT_EQ(tree.getDepth(child1), 1);
  EXPECT_EQ(tree.getDepth(child2), 1);
  EXPECT_EQ(tree.getDepth(grandchild1), 2);
  EXPECT_EQ(tree.getDepth(grandchild2), 2);
}

TEST(TreeTest, LeafAndRoot) {
  auto root = std::make_shared<Vertex<int>>(1);
  Tree tree{root};
  auto child1 = std::make_shared<Vertex<int>>(2);
  auto child2 = std::make_shared<Vertex<int>>(3);

  tree.insert(root, child1);
  tree.insert(root, child2);

  EXPECT_FALSE(tree.isLeaf(root));
  EXPECT_TRUE(tree.isLeaf(child1));
  EXPECT_TRUE(tree.isLeaf(child2));

  EXPECT_TRUE(tree.isRoot(root));
  EXPECT_FALSE(tree.isRoot(child1));
  EXPECT_FALSE(tree.isRoot(child2));
}

TEST(TreeTest, Clear) {
  auto root = std::make_shared<Vertex<int>>(1);
  Tree tree{root};
  auto child1 = std::make_shared<Vertex<int>>(2);
  auto child2 = std::make_shared<Vertex<int>>(3);

  tree.insert(root, child1);
  tree.insert(root, child2);

  tree.clear();

  EXPECT_EQ(tree.size(), 0);
  EXPECT_TRUE(tree.isEmpty());
  EXPECT_EQ(tree.getRoot(), nullptr);
}

TEST(TreeTest, EdgeCases) {
  Tree tree;

  EXPECT_TRUE(tree.isEmpty());
  EXPECT_EQ(tree.size(), 0);
  EXPECT_EQ(tree.getHeight(), 0);
  EXPECT_EQ(tree.getRoot(), nullptr);

  auto root = std::make_shared<Vertex<int>>(1);
  tree.setRoot(root);

  EXPECT_FALSE(tree.isEmpty());
  EXPECT_EQ(tree.size(), 1);
  EXPECT_EQ(tree.getHeight(), 1);
  EXPECT_EQ(tree.getRoot(), root);

  tree.remove(root);

  EXPECT_TRUE(tree.isEmpty());
  EXPECT_EQ(tree.size(), 0);
  EXPECT_EQ(tree.getHeight(), 0);
  EXPECT_EQ(tree.getRoot(), nullptr);
}

auto main(int argc, char* argv[]) -> int {
  ::testing::InitGoogleTest(&argc, argv);
  return RUN_ALL_TESTS();
}

*/