0

I have some experience with C. However I am trying out C++ and I decided to try and write some basic Tree implementations with C++. Here is how I define my TreeNode class

#include <iostream>
#include <string>

class BinaryTreeNode {
public:
    int data_;
    BinaryTreeNode *left_;
    BinaryTreeNode *right_;

    BinaryTreeNode(int d, BinaryTreeNode *l, BinaryTreeNode *r) : data_{ d }, left_{ l }, right_{ r } {}
    BinaryTreeNode(int d, BinaryTreeNode *l) : data_{ d }, left_{ l }, right_{ nullptr } {}
    BinaryTreeNode(int d) : data_{ d }, left_{ nullptr }, right_{ nullptr } {}
};

My Binary Search Tree class looks like,

class BST {
public:
    BinaryTreeNode *head_;
    void BST_Insert(BinaryTreeNode *&head, int data);
    BinaryTreeNode *BST_Search(BinaryTreeNode *root, int key);
};

I wrote 2 functions which are members of the BST class. They are an insert function and a search function. My insert and search functions are,

void BST::BST_Insert(BinaryTreeNode *&head, int data) {
    if (head == nullptr) {
        head = new BinaryTreeNode(data);
        return;
    }
    if (data > head->data_)
        BST_Insert(head->right_, data);
    else
        BST_Insert(head->left_, data);
    return;
}

BinaryTreeNode* BST::BST_Search(BinaryTreeNode *root, int key) {
    if (root == nullptr || root->data_ == key)
        return root;
    if (key > root->data_)
        return BST_Search(root->right_, key);
    else
        return BST_Search(root->left_, key);
}

In the main function I have written code to create the following tree
enter image description here

int main() {
    BST bst;
    bst.BST_Insert(bst.head_, 3);
    bst.BST_Insert(bst.head_, 5);
    bst.BST_Insert(bst.head_, 1);
    bst.BST_Insert(bst.head_, 2);
    BinaryTreeNode *oldptr = bst.head_;
    BinaryTreeNode *found_1 = bst.BST_Search(bst.head_, 1);
    return 0;
}

I can see that both BinaryTreeNode *oldptr = bst.head_; and BinaryTreeNode *found_1 = bst.BST_Search(bst.head_, 1); are causing segmentation faults to happen. Is there a way to fix this or is there an issue with my implementation?

senior_mle
  • 809
  • 1
  • 10
  • 20
  • 1
    For one your BST doesn't have a constructor initializing head to nullptr. BST_Search should not get bst.head_ as parameter it should know that internally in the class. Try to learn how to use a debugger to find out where the exception is thrown and to keep you member data private. ALL interaction with your BST should go throug functions! – Pepijn Kramer Oct 23 '22 at 04:17
  • 1
    `bst.BST_Insert(bst.head_, 3);` -- Why is the `BST_insert` function requiring that the caller pass `bst.head`? All I would expect would be `bst.BST_Insert(3); bst.BST_Insert(5); bst.BST_Insert(1);` etc.. Let the binary search tree class figure out how to add the node. The BST implementation shouldn't have its internals controlled by outside forces. – PaulMcKenzie Oct 23 '22 at 04:17
  • no need for those underscores on variable names – Neil Butterworth Oct 23 '22 at 04:22
  • 1
    @NeilButterworth I think this is a coding style to show it are member variables (like `m_` in other bits of code). – Pepijn Kramer Oct 23 '22 at 04:38
  • @PepijnKramer I am aware of that. Just wanted to code it in a way so as to able to print and check the validity of my tree from main function – senior_mle Oct 23 '22 at 04:45
  • @alpha93 I explained the exact same problem [here](https://stackoverflow.com/questions/74155692/why-sublime-text-not-showing-output-but-working-fine-in-online-compilers#comment130927291_74155692). The way to solve this is to initialize `head` with `nullptr`. – Jason Oct 23 '22 at 05:06
  • @alpha93 The problem is that in your original code, you didn't initialize `head` to `nullptr` which means it had indeterminate value. This means when inside the `BST::BST_Insert`, the condition ` if (head == nullptr)` is not satisfied. Thus in the next line when you do `if (data > head->data_)` you're dereferencing an uninitialized pointer and so have **undefined behavior**. – Jason Oct 23 '22 at 05:12

0 Answers0