CODEWITHSUNDEEP
c++binary-search-treebreadth-first-search
nym_kalahi
nym_kalahi

Reputation: 91

Breadth First Search of Binary Search Tree

I'm trying to make a breadth first search function for a binary search tree, but I don't seem to be able to make it work. Any pointers would be greatly appreciated!

template <class T>
bool BST<T>::displayBfs(T searchKey, BST<T> *node)
{
    BST<T> *tmp = node;
    queue <int> queue;
    queue.push(node->mData);

    if (node == NULL)
    {
        return false;    
    }

    while (!queue.empty())
    {
        queue.pop();
        if (tmp->mData == searchKey)
            return true;
        else
        {
            if(tmp->mLeft != NULL)
                queue.push(tmp->mLeft->mData);
            if(tmp->mRight != NULL)
                queue.push(tmp->mRight->mData);
        }
    }
    return false;
}

Upvotes: 0

Views: 6783

Answers (2)

codaddict
codaddict

Reputation: 455020

Few things:

The test for node == NULL should come before you access the node:

if (node == NULL)
    return false;    
queue.push(node);

Also your queue should be of node type and you should be inserting the nodes in the queue:

queue*> queue;

And finally you are not not accessing the dequed element, you need to use the front method of the queue class to access the front element before you call pop.

Upvotes: 0

Murilo Vasconcelos
Murilo Vasconcelos

Reputation: 4827

Since the BST<T> nodes have the information about their children, you have to put them on the queue, not the values as you are doing. Other thing is that you ain't getting the element from the queue before popping it. And finally you have to give other name to your queue because of the std::queue I'm assuming you are using.

Try to rewrite your BFS this way:

template <class T>
bool BST<T>::displayBfs(T searchKey, BST<T> *node)
{
    if (node == NULL) return false;

    queue<BST<T>*> q;
    q.push(node);

    while (!q.empty())
    {
        BST<T>* tmp = q.front();
        q.pop();

        if (tmp->mData == searchKey)
            return true;
        else
        {
            if(tmp->mLeft != NULL)
                q.push(tmp->mLeft);
            if(tmp->mRight != NULL)
                q.push(tmp->mRight);
        }
    }
    return false;
}

Upvotes: 2

Related Questions