Segmentation Fault while searching a node in BST

Question

I have written a search function in Binary Search Tree. While the function works properly and does what it should when the key is present in the tree but gives a segmentation fault when it isn't. Also is it right to print "yes" or "no" or should this function return a pointer to node?

template<class T>
class Node{
public:
    T m_data;  
    Node<T>* m_left;
    Node<T>* m_right;

    Node(T data){
         m_data=data;
         m_left=nullptr;
         m_right=nullptr;
     }
};

template<class T>
class bst {
private:
    Node<T>* root;

public:
    bst() { root = nullptr; }
    ~bst() { deltree(root); }
    void addnode(Node<T>* node, T data) {
        
        if(this->root == nullptr) {
            Node<T>* new_node= new Node<T>(data);
            this->root = new_node;
        } else if(data > node->m_data) {
            if(node->m_right != nullptr) {
                addnode(node->m_right, data);
            } else {
                Node<T>* new_node = new Node<T>(data);
                node->m_right = new_node;
            }
        } else if(data < node->m_data) {
            if(node->m_left != nullptr) {
                addnode(node->m_left, data);
            } else {
                Node<T>* new_node = new Node<T>(data);
                node->m_left = new_node;
            }
        }
    }
    void addnode(T data) { addnode(this->root, data); }

    void searchkey(T data) { searchkey(data, this->root); }

    void searchkey(T data, Node<T>* node) {
        if(this->root == nullptr) {
            std::cout << "Empty :) ";
        }
        if(data == node->m_data) {
            std::cout << "Found";
        } else if(node->m_data > data) {
            searchkey(data, node->m_left);
        } else if(node->m_data < data) {
            searchkey(data, node->m_right);
        }

        else {
            std::cout << "NOt fOUND";
        }
    }

void deltree(Node<T>* node) {
        if(node) {
            deltree(node->m_left);
            deltree(node->m_right);
            delete node;
        }
};

Unrelated: I really expected to see a destructor in the bst class. — Ted Lyngmo
Note that you have a serious problem in void addnode(Node<T>* node, T data); - You create new Nodes recursively. You should only create it when you've found a slot for the data, otherwise you create a lot of Nodes that you leak. You also need a destuctor. example — Ted Lyngmo
Okay, I will take care of this. Thanks for pointing out! @TedLyngmo — user10057478

brc-dd brc-dd · Accepted Answer · 2020-07-17T05:16:58

You are not checking if the node is null and hence are trying to access members (m_data, m_left, m_right) on a potentially empty node. Adding just a check is what you need.

Use this:

void searchkey(T data) {
  if (this->root == nullptr) {             // <-- check if root is null in this function not
    std::cout << "Empty :) " << std::endl; //     the other one to reduce number of comparisons
  } else {
    searchkey(data, this->root);
  }
}

void searchkey(T data, Node<T> *node) {
  if (node == nullptr) {                   // <-- check if node is null
    std::cout << "Not found" << std::endl;
  } else if (node->m_data > data) {
    searchkey(data, node->m_left);
  } else if (node->m_data < data) {
    searchkey(data, node->m_right);
  } else {
    std::cout << "Found" << std::endl;
  }
}

UPDATE :

It is better to return a pointer to node from such a function. If you are just checking then at anytime you can do so by directly comparing the result with nullptr. Overall, its your choice how you wanna implement it, and whether or not you aim to get a pointer to node.

UPDATE - 2 :

Improvised code by Ted Lyngmo: (Fixed memory leaks in addnode, simplified code and added destructor)

#include <iostream>

template<class T>
class bst {
private:
    struct Node {
        T m_data;
        Node* m_left = nullptr;
        Node* m_right = nullptr;

        Node(T data) : m_data(data) {}
    };

    Node* root = nullptr;

    void addnode(Node*& node, T data) {
        if(node == nullptr) {
            node = new Node(data);
        } else if(data > node->m_data) {
            addnode(node->m_right, data);
        } else if(data < node->m_data) {
            addnode(node->m_left, data);
        } else {
            std::cout << "Already Exists\n";
        }
    }

    void searchkey(T data, Node* node) {
        if(node == nullptr) {
            std::cout << "Not Found\n";
        } else if(data < node->m_data) {
            searchkey(data, node->m_left);
        } else if(node->m_data < data) {
            searchkey(data, node->m_right);
        } else {
            std::cout << "Found\n";
        }
    }

    void deltree(Node* node) {
        if(node) {
            deltree(node->m_left);
            deltree(node->m_right);
            delete node;
        }
    }

public:
    ~bst() { deltree(root); }

    void addnode(T data) { addnode(root, data); }
    void searchkey(T data) { searchkey(data, root); }
};

int main() {
    bst<int> b;
    b.addnode(10);
    b.addnode(12);
    b.addnode(11);
    b.searchkey(11);
}

Segmentation Fault while searching a node in BST

1 Answers