#### Trying to understand my mistakes – Beginner needs advice on how to make this dsi work

I have successfully completed 9 data structure exercises in C++ but the binary search tree dsi is stumping me. After it is compiled, everything looks fine, however when i try to execute this program, it crashed.

I would really appreciate some mentorship as to where my code goes wrong and how I might fix it.

``````#ifndef BINARYSEARCHTREE_HPP
#define BINARYSEARCHTREE_HPP

#include <iostream>

class BSTNode {
public:
int data;
BSTNode* left;
BSTNode* right;
BSTNode* parent;

BSTNode(int value) {
data = value;
left = nullptr;
right = nullptr;
parent = nullptr;
}

~BSTNode() {
delete left;
delete right;
}
};

class BinarySearchTree {
private:
BSTNode* root;

BSTNode* maximum(BSTNode* node) {
if(node == nullptr) {
return nullptr;
}
while (node->right != nullptr) {
node = node->right;
}
return node;
}

void replaceSubtree(BSTNode* oldSubtree, BSTNode* newSubtree) {
if (oldSubtree->parent == nullptr) {
root = newSubtree;
} else if (oldSubtree == oldSubtree->parent->left) {
oldSubtree->parent->left = newSubtree;
} else {
oldSubtree->parent->right = newSubtree;
}
if (newSubtree != nullptr) {
newSubtree->parent = oldSubtree->parent;
}
}

void print(BSTNode* node) {
if (node != nullptr) {
print(node->left);
std::cout << node->data << " ";
print(node->right);
}
}

public:
BinarySearchTree() {
root = nullptr;
}

BSTNode* predecessor(BSTNode* node) {
if (node->left != nullptr) {
return maximum(node->left);
}
BSTNode* y = node->parent;
while (y != nullptr && node == y->left) {
node = y;
y = y->parent;
}
return y;
}

void insert(int value) {
BSTNode* node = new BSTNode(value);
BSTNode* y = nullptr;
BSTNode* x = root;

while (x != nullptr) {
y = x;
if (node->data < x->data) {
x = x->left;
} else {
x = x->right;
}
}

node->parent = y;
if (y == nullptr) {
root = node;
} else if (node->data < y->data) {
y->left = node;
} else {
y->right = node;
}
}

BSTNode* searchNode(int val) {
BSTNode* x = root;
while (x != nullptr && val != x->data) {
if (val < x->data) {
x = x->left;
} else {
x = x->right;
}
}
return x;
}

bool search(int val) {
return searchNode(val) != nullptr;
}

void remove(int value) {
BSTNode* node = searchNode(value);
if (node == nullptr) {
return;
}
if (node->left != nullptr) {
replaceSubtree(node, node->right);
} else if (node->right != nullptr) {
replaceSubtree(node, node->left);
} else {
BSTNode* y = maximum(node->left);
if (y != nullptr && y->parent != node) {
replaceSubtree(y, y->left);
if (y->left != nullptr) {
y->left->parent = y;
}
}
replaceSubtree(node, y);
if (y->right != nullptr) {
y->right->parent = y;
}
}
node->left = nullptr; // Set node's left and right pointers to null before deletion
node->right = nullptr;
delete node;
}

void print() {
print(root);
std::cout << std::endl;
}
};

#endif
``````

New contributor

Michael Wells is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.