Segmentation fault for inserting into an BST

Question

So for this class here, I have to write out functions, including a recursive find function, an insert function, and a operator[] function, which overall helps insert into a BST

#include <compare>
#include <cstddef>
#include <format>
#include <iostream>
#include <string>
#include <utility>


template<typename Key, typename Value>
struct BST
{
  using KeyValue_Pair = std::pair<Key const, Value>;

  struct Node
  {
    Node() = default;
    Node( KeyValue_Pair const & pair ) : _pair{ pair } {}

    KeyValue_Pair _pair = { Key{}, Value{} };

    Node * _left   = nullptr;
    Node * _right  = nullptr;
    Node * _parent = nullptr;
  };

  Node *      _root = nullptr;
  std::size_t _size = 0;


Node * find( Key const & key )
 {
   return find(key, _root);  // Delegate the call to the private helper function
 }

Node* find(Key const& key, Node* current) {
    // Base Case: Node not found
    if (current == nullptr) {
        return nullptr;
    }

    // Visit: Node found
    if (key == current->_pair.first) {
        return current;
    }

    // Recurse: Search left or right subtree
    if (key < current->_pair.first) {
        return find(key, current->_left);
    } else {
        return find(key, current->_right);
    }
}

Node * insert( KeyValue_Pair const & pair ) {
     Node * newNode = new Node( pair );
     if(_root == nullptr){
      _root = newNode;
      ++_size;
      return newNode;
    }
    Node * current = _root;
    Node * parent  = nullptr;

    while(current != nullptr){
      parent = current;
      auto comp   = std::compare_weak_order_fallback( pair.first, current->_pair.first );
      if( comp == 0 ) return current;
      else if(comp < 0 ) current = current->_left;
      current = current->_right;
    }
    auto comp = std::compare_weak_order_fallback( pair.first, current->_pair.first );
    if( comp < 0 ) parent->_left = newNode;
    else parent->_right = newNode;

    newNode->_parent = parent;
    ++_size;
    return newNode;
}

Value & operator[]( Key const & key )
{
  return insert( { key, Value{} } )->_pair.second;
}   

//everything under this comment already came with the code
void print()
{
  auto count = 0uz;
  print( _root, count );
}

void print( Node * current, std::size_t & count )  // in-order traversal
{
  // Base case
  if( current == nullptr ) return;

  // Recurse left
  print( current->_left, count );

  // Visit
  auto && [key, value] = current->_pair;
  std::cout << std::format( "{:3}:  {{{}, {}}}\n", ++count, key, value );

  // Recurse right
  print( current->_right, count );
}

~BST() noexcept
{ clear(); }
};

int main()
{
  BST<unsigned int, std::string> myTree;

  std::cout << "Test Case 1:\n";                     //          50         //
  myTree[50] = "indeed";                             //        /   \        //
  myTree.insert( { 40, "Structures" } );             //       40    60      //
  myTree.insert( { 60, "very" } );                   //      / \   / \      //
  myTree.insert( { 30, "Lego" } );                   //     30 45 55  70    //
  myTree.insert( { 45, "are" } );
  myTree[55] = "truly";
  myTree[70] = "entertaining";
  myTree.print();
  std::cout << "------------------------------\n";
}

yet, I get a segmentation fault (core dumped) error message for test case 1. I'm not sure if the error is in the recursive find or insert function. I would greatly appreciate some feedback, please and thank you. I also apologize if the code is too long, I wanted to include the test case 1 from main but I wasn't sure if I should include the void print functions or not.

Answer 1

Your while loop either exits when it finds a match or when it runs out of the bottom -- at which point current is null. The very next statement dereferences current. You maybe mean parent. Is this the output you expect:

  1:  {30, Lego}
  2:  {40, Structures}
  3:  {45, are}
  4:  {50, indeed}
  5:  {55, truly}
  6:  {60, very}
  7:  {70, entertaining}

That's what I got when I made two changes:

cout << "while....\n";
    while(current != nullptr){
      parent = current;
      auto comp   = std::compare_weak_order_fallback( pair.first, current->_pair.first );
      if( comp == 0 ) return current;
      else if(comp < 0 ) current = current->_left;
      else current = current->_right;
    }
cout << "while done\n";
    auto comp = std::compare_weak_order_fallback( pair.first, parent->_pair.first );

See the else-clause at the end of the while loop (you were just setting it) and the dereference of parent instead of current.