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, Jul 17 '20 at 05:26
Note that you have a serious problem in `void addnode(Node* node, T data);` - You create new `Node`s recursively. You should only create it when you've found a slot for the data, otherwise you create a lot of `Node`s that you leak. You also need a destuctor. [example](https://godbolt.org/z/Pqs71s) — Ted Lyngmo, Jul 17 '20 at 06:25
Okay, I will take care of this. Thanks for pointing out! @TedLyngmo — , Jul 17 '20 at 10:11
Much better. That shouldn't leak. You can make `addnode` a lot simpler though (as I showed in the example), but this'll work. — Ted Lyngmo, Jul 17 '20 at 10:32

brc-dd · Accepted Answer · 2020-07-17T14:46:16.473

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);
}

Just a query! when the pointer reaches on the leaf node how does it know "node==nullptr"? 12 / \ 10 14 / \ / \ 8 11 13 15 What if am trying to find a node with key 112? How does it know "Not Found". — , Jul 17 '20 at 05:45
@TedLyngmo My bad. Doesn't work. :/ https://stackoverflow.com/a/9286551/11613622 — brc-dd, Jul 17 '20 at 05:49
@Tushar It isn't `nullptr` on the leaf node. But when you're on leaf node then either `m_left` or `m_right` is going to be null, which you are passing to the function in the recursive call. — brc-dd, Jul 17 '20 at 05:52

Segmentation Fault while searching a node in BST

1 Answers1