Currently doing an assignment where we have to make a binary search tree (I'm using a linked list implementation) and I'm currently getting stuck trying to find the adjacency of nodes given two nodes. It is marked against input that is hidden, I'll provide my code and test cases that I can't fulfill. This is my first time writing a question on Stack Overflow let me know how to word my questions better and/or provide more detailed information. Also I'm not sure if I'm allowed to post my code from the assignment so I might have to take it down.
My implementation as far:
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <limits>
#include <utility>
#include <algorithm>
#include <string>
#include <cstdlib>
#include <cmath>
#include <memory>
using namespace std;
template <typename T> // the template allows the weight of vertex to take any numeric data type (denoted by T).
class BST {
private:
struct TreeNode {
T weight;
string name;
std::unique_ptr<TreeNode> left;
std::unique_ptr<TreeNode> right;
TreeNode(T weight, string name): weight(weight), name(name), left(nullptr), right(nullptr) {}
};
std::unique_ptr<TreeNode> root;
public:
/* define your data structure to represent a binary search tree (bst) */
map<string, T> vertices;
vector<string> leaves;
vector<pair<string,string>> edges;
bool adjacent_found = false;
/* test1 */
BST(); // the contructor function.
~BST(); // the destructor function.
size_t num_vertices(); // returns the total number of vertices in the bst.
void count(int& , const std::unique_ptr<TreeNode>&);
size_t num_edges(); // returns the total number of edges in the bst.
T sum_weight(); // return the total weight of all the vertices in the bst.
void weight_total(int& , const std::unique_ptr<TreeNode>&);
void print();
std::string TreeToString(const std::unique_ptr<TreeNode>& ); // Helper method for Print()
/* test2 */
void add_vertex(const string&, const T&); // adds a vertex, which has a weight, to the tree -- every vertex uses a string as its unique identifier.
void Insert(const T&, const string&, std::unique_ptr<TreeNode>&);
bool contains(const string&); // checks if a vertex is in the bst -- returns true if the bst contains the given vertex; otherwise, returns false.
bool Contains(const string&);
/* test3 */
vector<string> get_vertices(); // returns a vector of all the vertices in the bst.
vector<string> get_leaves(); // returns a vector of all the leaves in the bst.
// Leaves are the vertices that do not have any children in the bst.
void extract_leaf_nodes(std::unique_ptr<TreeNode>&);
/* test4 */
bool adjacent(const string&, const string&); // check if there is an edge between the two vertices in the bst -- returns true if the edge exists; otherwise, returns false.
void Adjacent(const string &, const string&, std::unique_ptr<TreeNode>&);
/* test5 */
vector<pair<string,string>> get_edges(); // returns a vector of all the edges in the bst -- each edge is represented by a pair of vertices incident to the edge.
void edge_retrieval(std::unique_ptr<TreeNode>&);
/* test6 */
vector<string> get_neighbours(const string&); // returns a vector of all the vertices, each of which is directly connected with the given vertex via an edge.
size_t degree(const string&); // returns the degree of a vertex.
/* test7 */
vector<string> preorder_traversal(); // returns a vector of all the vertices in the visiting order of a preorder traversal over the bst.
/* test8 */
vector<string> inorder_traversal(); // returns a vector of all the vertices in the visiting order of an inorder traversal over the bst.
/* test9 */
vector<string> postorder_traversal(); // returns a vector of all the vertices in the visiting order of a postorder traversal over the bst.
/* test10 */
vector<string> breadth_first_traversal(); // returns a vector of all the vertices in the visiting order of a breadth first traversal over the bst.
/* test11 */
vector<string> path(const string&, const string&); // returns a vector of all the vertices in the path from the first vertex to the second vertex.
// A path should include the source and destination vertices at the begining and the end, respectively.
/* test12 */
vector<string> path_with_largest_weight(); // returns a path that has the largest weight in the bst.
// The weight of a path is the sum of the weights of all the vertices (including the source and destination vertices) in the path.
/* test13 */
size_t height(); // returns the height of bst. Height of a tree is the number of edges that form the longest path from root to any leaf.
/* test14 */
void remove_vertex(const string&); // delete the given vertex from bst -- note that, all incident edges of the vertex should be deleted as well.
};
/* test1 */
template <typename T>
BST<T>::BST() {
root = nullptr;
}
template <typename T>
BST<T>::~BST() {}
template <typename T>
size_t BST<T>::num_vertices() {
int total_vertices = 0;
this->count(total_vertices,this->root);
return total_vertices;
}
template <typename T>
void BST<T>::count(int& total_vertices, const std::unique_ptr<TreeNode>& node) {
if (node != nullptr) {
total_vertices++;
this->count(total_vertices, node->left);
this->count(total_vertices, node->right);
}
}
template <typename T>
void BST<T>::weight_total(int& total_weight, const std::unique_ptr<TreeNode>& node) {
if (node != nullptr) {
total_weight += node->weight;
this->weight_total(total_weight,node->left);
this->weight_total(total_weight,node->right);
}
}
template <typename T>
size_t BST<T>::num_edges() {
if (num_vertices() != 0) {
return (this->num_vertices() - 1);
} else {
return 0;
}
}
template <typename T>
T BST<T>::sum_weight() {
int total_weight = 0;
this->weight_total(total_weight,this->root);
return total_weight;
}
template <typename T>
void BST<T>::print(){
if(this->root == nullptr){
std::cout << "{}" << std::endl;
} else{
std::cout << this->TreeToString(this->root) << std::endl;
}
}
template <typename T>
std::string BST<T>::TreeToString(const std::unique_ptr<TreeNode>& node) {
std::string leftStr = (node->left == nullptr) ? "{}" : TreeToString(node->left);
std::string rightStr = (node->right == nullptr) ? "{}" : TreeToString(node->right);
std::string result = "{" + (node->name) + ", " + leftStr + ", " + rightStr + "}";
return result;
}
/* test2 */
template <typename T>
void BST<T>::add_vertex(const string& u, const T& w) {
this->Insert(w, u, this->root);
}
template <typename T>
void BST<T>::Insert(const T& w, const string& vertice_name, std::unique_ptr<TreeNode>& node) {
if(node == nullptr){
// Make a new TreeNode for it to point to
node = std::make_unique<TreeNode>(w, vertice_name);
//cout << vertice_name << " : " << w << " | ";
vertices.insert(make_pair(vertice_name, w));
//cout << "Node: " << '"' << node->name << '"' << " | " << node->weight << endl;
} else{
if( w < node->weight) {
//cout << "Going left because w is: " << w << " and weight of node is: " << node->weight << endl;
// Case: w is < node's weight
this->Insert(w, vertice_name, node->left);
} else{
this->Insert(w, vertice_name, node->right);
}
}
}
template <typename T>
bool BST<T>::contains(const string& u) {
return Contains(u);
}
template <typename T>
bool BST<T>::Contains(const string& _name) {
for (auto& [key, value]: vertices) {
if (key == _name) {
return true;
}
}
return false;
}
/* test3 */
template <typename T>
vector<string> BST<T>::get_vertices() {
vector<string> get_vertices_vector;
for (auto& [key, value]: vertices) {
get_vertices_vector.push_back(key);
}
return get_vertices_vector;
}
template <typename T>
vector<string> BST<T>::get_leaves() {
extract_leaf_nodes(this->root);
return leaves;
}
template <typename T>
void BST<T>::extract_leaf_nodes(std::unique_ptr<TreeNode>& node) {
// if node is leaf node, copy name
if (!node->left && !node->right)
{
leaves.push_back(node->name);
}
// if left child exists, check for leaf
// recursively
if (node->left) {
extract_leaf_nodes(node->left);
}
// if right child exists, check for leaf
// recursively
if (node->right)
extract_leaf_nodes(node->right);
}
/* test4 */
template <typename T>
bool BST<T>::adjacent(const string& u, const string& v) {
adjacent_found = false;
if (this->contains(u) && this->contains(v)) {
Adjacent(u, v, this->root);
}
return adjacent_found;
}
template <typename T>
void BST<T>::Adjacent(const string & u, const string& v, std::unique_ptr<TreeNode>& node ) {
if (node != nullptr) {
if (node->name == v && node->left != nullptr && node->right != nullptr) {
if (node->right->name == u) {
adjacent_found = true;
} else if (node->left->name == u) {
adjacent_found = true;
}
} else if (node->name == u && node->left != nullptr && node->right != nullptr) {
if (node->right->name == v) {
//return true;
adjacent_found = true;
} else if (node->left->name == v) {
adjacent_found = true;
} else {
// Not Adjacent
}
} else {
// Can't find either
if (node->left != nullptr) {
Adjacent(u,v,node->left);
} else if (node->right != nullptr) {
Adjacent(u,v,node->right);
}
}
}
}
/* test5 */
template <typename T>
vector<pair<string,string>> BST<T>::get_edges() {
edge_retrieval(this->root);
return edges;
}
template <typename T>
void BST<T>::edge_retrieval(std::unique_ptr<TreeNode>& node) {
for (auto x : edges) {
if (x.first == node->name) {
edge_retrieval(node->left);
edge_retrieval(node->right);
} else {
if (node->left != nullptr) {
edges.push_back(make_pair(node->name,node->left->name));
}
else if (node->right != nullptr) {
edges.push_back(make_pair(node->name,node->right->name));
}
}
}
}
/* test6 */
template <typename T>
vector<string> BST<T>::get_neighbours(const string& u) {
return vector<string>();
}
template <typename T>
size_t BST<T>::degree(const string& u) {
vector<string> neighbours = get_neighbours(u);
return neighbours.size();
}
/* test7 */
template <typename T>
vector<string> BST<T>::preorder_traversal() {
return vector<string>();
}
/* test8 */
template <typename T>
vector<string> BST<T>::inorder_traversal() {
return vector<string>();
}
/* test9 */
template <typename T>
vector<string> BST<T>::postorder_traversal() {
return vector<string>();
}
/* test10 */
template <typename T>
vector<string> BST<T>::breadth_first_traversal() {
return vector<string>();
}
/* test11 */
template <typename T>
vector<string> BST<T>::path(const string& u, const string& v){
return vector<string>();
}
/* test12 */
template <typename T>
vector<string> BST<T>::path_with_largest_weight(){
return vector<string>();
}
/* test13 */
template <typename T>
size_t BST<T>::height() {
return 0;
}
/* test14 */
template <typename T>
void BST<T>::remove_vertex(const string& u) {
}
Test Cases: (v2 is adjacent to v3, but is returning that its not. And v2 is adjacent to v10 but also returning its not)
#include "tree.hpp"
int main(){
BST<int> bst;
bst.add_vertex("v1", 15);
bst.add_vertex("v4", 5);
bst.add_vertex("v0", 10);
bst.add_vertex("v3", 30);
bst.add_vertex("v2", 17);
bst.add_vertex("v5", 1);
bst.add_vertex("v7", 3);
bst.add_vertex("v6", 20);
bst.add_vertex("v8", 12);
bst.add_vertex("v9", 7);
bst.add_vertex("v10", 30);
bst.add_vertex("v11", 28);
bst.add_vertex("v12", 16);
bst.add_vertex("v13", 21);
bst.add_vertex("v14", 24);
bst.add_vertex("v15", 36);
bst.add_vertex("v16", 14);
bst.add_vertex("v17", 14);
cout << "is v2 adjacent to v3?:" << bst.adjacent("v2","v3") << endl;
cout << "is v2 adjacent to v10?:" << bst.adjacent("v2","v10");
}
