I am trying to implement a BST in C/C++.
Note: In this class, submissions are expected to have a .cpp file extension and should compile with a C++ compiler, but should be "philosophically" C (printf(), malloc(), etc.), with certain C++ features allowed (native bools, etc.). This also means working around C++ restrictions (casting the result of malloc(), adding const to strings, etc.). The line is fuzzy, so to be safe I am doing it C style - this is a personal project that I hope to be able to recycle when needed by simply adapting a few key functions.
I have a function pushBST() that calls pushBSTNode():
bool pushBST(BST* tree, const char* val_cstr, int val_int) {
if (tree == NULL) return false;
BSTData* data = createBSTData(val_cstr, val_int);
if (data == NULL) return false;
return pushBSTNode(tree->root, tree->root, data);
}
bool pushBSTNode(BSTNode* node, BSTNode* parent, BSTData* data) {
if (node == NULL) {
node = createBSTNode(data, parent);
if (node == NULL) return false;
return true;
} else {
// ...
}
}
My idea here is to abstract away pushing data to the BST with pushBST(), requiring only the tree itself and the raw data. However, this doesn't work, despite returning true. A peek into it with GDB in VSCode tells me that something is up, but I can't quite understand it.
Calling the function works as expected initially:
if (tree == NULL) return false; // So it doesn't choke on a void pointer, passed
BSTData* data = createBSTData(...); // It packed the data correctly, passed
if (data == NULL) return false; // Report a failure if the data failed to pack, passed.
At this point, I can see the variables are correct: the tree exists and the data is packed with the correct values. Following it is the function to actually push it:
if (node == NULL) { // tree->root was indeed NULL, passed
node = createBSTNode(...); // This allocates a node and assigns it the packed data, passed
if (node == NULL) return false; // The node exists, passed
return true; // Therefore, this should have worked
}
The node that was passed in refers to tree->root, so it should have allocated a node structure there. At the end of that function, it is indeed true that the node variable has the data and the data is correct (the variable parent is wrong, but I'm going to work on it later). However, upon returning to the main push function, I see the variable hasn't changed. The variable tree->root is still NULL, but now it has a return value, indicating a supposed success.
Any ideas on what went wrong and how I can fix it?
Here is the test program I use:
main.cpp:
#include <stdio.h>
#include "bstree.hpp"
int main() {
myds::bst::BST* tree = myds::bst::createBST();
myds::bst::pushBST(tree, "yeet val 1", 5);
myds::bst::pushBST(tree, "yeet val 2", 3);
myds::bst::pushBST(tree, "yeet val 3", 4);
myds::bst::pushBST(tree, "yeet val 4", 1);
myds::bst::pushBST(tree, "yeet val 5", 2);
printf("Hello World!\n");
return 0;
}
bstree.hpp:
#ifndef BSTREE_HPP
#define BSTREE_HPP
#include <stddef.h>
namespace myds::bst {
struct BSTData {
char val_cstr[16];
int val_int
};
struct BSTNode {
BSTData* data;
BSTNode* parent;
BSTNode* left;
BSTNode* right;
};
struct BST {
BSTNode* root;
};
BSTData* createBSTData(const char* val_cstr, int val_int);
BSTNode* createBSTNode(BSTData* data, BSTNode* parent);
BST* createBST();
bool pushBSTNode(BSTNode* node, BSTNode* parent, BSTData* data);
bool pushBST(BST* tree, const char* val_cstr, int val_int);
}
#endif
bstree.cpp:
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include "bstree.hpp"
namespace myds::bst {
BSTData* createBSTData(const char* val_cstr, int val_int) {
BSTData* data = (BSTData*) malloc(sizeof(BSTData));
if (data == NULL) return NULL;
strcpy(data->val_cstr, val_cstr);
data->val_int = val_int;
return data;
}
BSTNode* createBSTNode(BSTData* data, BSTNode* parent) {
BSTNode* node = (BSTNode*) malloc(sizeof(BSTNode));
if (node == NULL) return NULL;
node->data = data;
node->parent = parent;
node->left = NULL;
node->right = NULL;
return node;
}
BST* createBST() {
BST* tree = (BST*) malloc(sizeof(BST));
if (tree == NULL) return NULL;
tree->root = NULL;
return tree;
}
bool pushBSTNode(BSTNode* node, BSTNode* parent, BSTData* data) {
if (node == NULL) {
node = createBSTNode(data, parent);
if (node == NULL) return false;
return true;
} else {
ssize_t delta = compareBSTData(data, node->data);
if (delta < 0) {
// data is smaller than current node, should go to left side of node
return pushBSTNode(node->left, node, data);
} else if (delta == 0) {
// data == node, cannot store duplicate values
return false;
} else if (delta > 1) {
// data is larger than current node, should go to the right side of node
return pushBSTNode(node->right, node, data);
}
}
return false; // silence clang
}
bool pushBST(BST* tree, const char* val_cstr, int val_int) {
if (tree == NULL) return false;
BSTData* data = createBSTData(val_cstr, val_int);
if (data == NULL) return false;
bool retval = pushBSTNode(tree->root, tree->root, data);
return retval;
}
}
Pointers used for propagation of the tree need to be passed by reference. If you pass by value (without reference), any changes made within the scope of your CreateBSTNode function are lost when the function is complete.
pushBSTNode(BSTNode* &node, BSTNode* &parent, BSTData* &data)