Search Function Implementation in Binary Search Tree

Admin 1
Viewed 83

I have implemented a function "searchkey" in order to return a node in a binary search tree if the key is present but it is returning the root node. I have added a minimal reproducible code.
While the same iterative method works. Also which would be the better way to implement this recursive or iterative.

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); }
    
         Node<T>* searchkey(T data) { 
            return searchkey(data,this->root);
    }
    
            Node<T>* searchkey(T data, Node<T> *node) {
        if (node == nullptr) { // <-- check if node is null
            return node;
        } else if (data == node->m_data) {
            return node;
        } else if (node->m_data > data) {
            searchkey(data, node->m_left);
        } else if (node->m_data < data) {
            searchkey(data, node->m_right);
        }
        return node;
    }
    
    void deltree(Node<T>* node) {
            if(node) {
                deltree(node->m_left);
                deltree(node->m_right);
                delete node;
            }
    };
binary-search-tree search c++
1 Answers

It seems you are missing a few return statements in your search function. Also, the test for data == node->m_data isn't needed. The fallback return at the end of the function means that a match is found if you return when doing the recursive calls.

Node<T>* searchkey(T data, Node<T> *node) {
    if (node == nullptr) { // <-- check if node is null
        return node;
    } else if (node->m_data > data) {
        return searchkey(data, node->m_left);
    } else if (node->m_data < data) {
        return searchkey(data, node->m_right);
    }
    return node; // match found
}

In your original code, you called searchkey but did not return the value it returned. The function instead continued to return the same node that was given as an argument to the function, yielding the wrong result in all cases except when searching for the value stored in the root node.

An alternative view:

Node<T>* searchkey(T data, Node<T> *node) {
    if (node != nullptr) {
        if (node->m_data > data) {
            node = searchkey(data, node->m_left);
        } else if (node->m_data < data) {
            node = searchkey(data, node->m_right);
        } // else { here we know that node->m_data == data }
    }
    return node; // nullptr or the matching Node* is returned
}

Also which would be the better way to implement this recursive or iterative.

There's no definite answer. If you are likely to store many values, so the search depth becomes large, you don't want recursive calls because you may then get a stack overflow.

user_75822470
Related