#ifndef TREE_H
#define TREE_H

#include <vector>
using namespace std;

class Tree
{
public:
  /** Construct an empty tree */
  Tree()
  {
  }

  /** Construct a tree with root, parent, and searchOrder */
  Tree(int root, vector<int> &parent, vector<int> &searchOrders)
  {
    this->root = root;
    this->parent = parent;
    this->searchOrders = searchOrders;
  }

  /** Return the root of the tree */
  int getRoot() const
  {
    return root;
  }

  /** Return the parent of vertex v */
  int getParent(int v) const
  {
    return parent[v];
  }

  /** Return search order */
  vector<int> getSearchOrders() const
  {
    return searchOrders;
  }

  /** Return number of vertices found */
  int getNumberOfVerticesFound() const
  {
    return searchOrders.size();
  }

  /** Return the path of vertices from v to the root in a vector */
  vector<int> getPath(int v) const
  {
    vector<int> path;

    do
    {
      path.push_back(v);
      v = parent[v];
    }
    while (v != -1);

    return path;
  }

  /** Print the whole tree */
  void printTree() const
  {
    cout << "Root is: " << root << endl;
    cout << "Edges: ";
    for (int i = 0; i < searchOrders.size(); i++) {
      if (parent[searchOrders[i]] != -1) {
        // Display an edge
        cout << "(" << parent[searchOrders[i]] << ", " <<
          searchOrders[i] << ") ";
      }
    }
    cout << endl;
  }

private:
  int root; // The root of the tree
  vector<int> parent; // Store the parent of each vertex
  vector<int> searchOrders; // Store the search order
};
#endif