C++

Forum

 
Search function only finds first value

Pages: 12
rubito (28)
I'm implementing the search function of a binary search tree and it seems as though it's not searching all of the values, just the first one.

I have a public search function that when called it calls the private search function
1
2
3
4
5
 
template<typename T>
Node<T>* BinarySearchTree<T>::search(T value)
{
    return search(value, m_root);
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
template<typename T>
Node<T>* BinarySearchTree<T>::search(T value, Node<T>*subtree)
{
    if (subtree->getValue() == value)
    {
        Node<T>* nodePtr = new Node<T>();
        nodePtr->setValue(value);// = value;
        return nodePtr;
    }
    if ((subtree->getLeft() == nullptr && subtree->getRight()) == nullptr)
    {
        return nullptr;
    }
    if (value < subtree->getValue())
    {
        if(subtree->getLeft() == nullptr )
        return NULL;
        return search(value,subtree->getLeft());
    }
    if (value > subtree->getValue())
    {
        if(subtree->getRight() == nullptr )
        return NULL;
        return search(value,subtree->getRight());
    }
}


Here's a sample output
*note that my print function is also acting up, but my main focus is the search function.

Input a number to put in the tree: 5
Done adding numbers? (y/n): n
Input a number to put in the tree: 3
Done adding numbers? (y/n): n
Input a number to put in the tree: 4
Done adding numbers? (y/n): y

Tree currently has the following values:
Here
0 Here
Here
5 Here
3 Here
Here
4 Here
Here
Here

Here are sorted values:
4 3 5

Input a number to search for in the tree: 5
5 is in the tree!
Done searching numbers? (y/n): n
Input a number to search for in the tree: 4
Sorry, 4 was not in the tree
Done searching numbers? (y/n): n
Input a number to search for in the tree: 3
Sorry, 3 was not in the tree
Done searching numbers? (y/n): y

Goodbye!

Process returned 0 (0x0) execution time : 31.518 s
Press ENTER to continue.


Any help would be greatly appreciated.
Thanks
helios (17574)
Looks correct. Maybe the tree is incorrectly built.
rubito (28)
I thought so too. Could you take a look at my add function. This is what builds the tree. I think its creating it in a way where there's only one branch but I can't figure out if that's the case or if I'm doing something else wrong? 

1
2
3
4
5
6
7
8
9
10
11
12
13
 
 
template<typename T>
void BinarySearchTree<T>::add(T value)
{
    if (m_root == nullptr)
    {
        Node<T>* node = new Node<T>;
        node->setValue(value);
        m_root = node;
    }
    else
        add(value, m_root);
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
template<typename T>
void BinarySearchTree<T>::add(T value, Node<T>* subtree)
{
    if (value < subtree->getValue())
    {
        if(subtree->getLeft() == nullptr)
        {

            Node<T>* node = new Node<T>();
            node->setValue(value);
            subtree->setLeft(node);
        }
        else
        {
            add(value, subtree->getLeft());
        }
    }
    else if (value >= subtree->getValue())
    {
        if(subtree->getRight() == nullptr)
        {

        Node<T>* node = new Node<T>();
        node->setValue(value);
        subtree->setRight(node);
        }
        else
        {
            add(value, subtree->getRight());
        }
    }
}
helios (17574)
Still not seeing it. Could you post the whole thing?
rubito (28)
This is my whole BinarySearchTree.hpp file. I also have a main.cpp, BinarySearchTree.h, Node.h, and a Node.hpp. I didn't post them to keep this short. But I can if needed. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
 
 
/*#ifndef BINARYSEARCHTREE_HPP_INCLUDED
#define BINARYSEARCHTREE_HPP_INCLUDED'
*/
#include "BinarySearchTree.h"

template<typename T>
BinarySearchTree<T>::BinarySearchTree()
{
    m_root = new Node<T>;
    m_root->setValue(nullptr);
}

template<typename T>
BinarySearchTree<T>::~BinarySearchTree()
{
    delete m_root;
    m_root = nullptr;
}

template<typename T>
void BinarySearchTree<T>::add(T value)
{
    if (m_root == nullptr)
    {
        Node<T>* node = new Node<T>;
        node->setValue(value);
        m_root = node;
    }
    else
        add(value, m_root);
}

template<typename T>
void BinarySearchTree<T>::printTree()
{
    if (m_root == nullptr)
    {
        std::cout<<"Tree Empty";
    }
    else
    {
        printTree(m_root);//Node<T>* subtree);
    }
}
template<typename T>
void BinarySearchTree<T>::sortedPrint()
{
     if (m_root == nullptr)
     {
        std::cout<<"Tree Empty";
     }
     else
     {
         sortedPrint(m_root);
     }

}

template<typename T>
Node<T>* BinarySearchTree<T>::search(T value)
{
    return search(value, m_root);
}

//private members

template<typename T>
void BinarySearchTree<T>::add(T value, Node<T>* subtree)
{
    if (value < subtree->getValue())
    {
        if(subtree->getLeft() == nullptr)
        {

            Node<T>* node = new Node<T>();
            node->setValue(value);
            subtree->setLeft(node);
        }
        else
        {
            add(value, subtree->getLeft());
        }
    }
    else if (value >= subtree->getValue())
    {
        if(subtree->getRight() == nullptr)
        {

        Node<T>* node = new Node<T>();
        node->setValue(value);
        subtree->setRight(node);
        }
        else
        {
            add(value, subtree->getRight());
        }
    }
}

template<typename T>
void BinarySearchTree<T>::deleteTree(Node<T>* subTree)
{
    Node<T>* left = subTree->getLeft();
    Node<T>* right = subTree->getRight();
    if (left != nullptr)
    {
        deleteTree(left);
    }
    if (right != nullptr)
    {
        deleteTree(right);
    }
}

template<typename T>
void BinarySearchTree<T>::printTree(Node<T>* subtree)
{
    //std::cout << "Here" << std::endl;
    if (subtree != nullptr)
    {
        std::cout<<subtree->getValue()<<" ";
        printTree(subtree->getLeft());
        printTree(subtree->getRight());
    }
}

template<typename T>
void BinarySearchTree<T>::sortedPrint(Node<T>* subtree)
{
    if (subtree != nullptr)
    {
        if (subtree->getLeft()!=nullptr)
        {
            sortedPrint(subtree->getLeft());
            std::cout<<subtree->getLeft()->getValue()<<" ";
	}

        if (subtree->getRight()!=nullptr)
            {
                sortedPrint(subtree->getRight());
                std::cout<<subtree->getRight()->getValue()<<" ";
            }
    }
}

template<typename T>
Node<T>* BinarySearchTree<T>::search(T value, Node<T>*subtree)
{
    if (subtree->getValue() == value)
    {
        Node<T>* nodePtr = new Node<T>();
        nodePtr->setValue(value);// = value;
        return nodePtr;
    }
    if ((subtree->getLeft() == nullptr && subtree->getRight()) == nullptr)
    {
        return nullptr;
    }
    if (value < subtree->getValue())
    {
        if(subtree->getLeft() == nullptr )
        return NULL;
        return search(value,subtree->getLeft());
    }
    if (value > subtree->getValue())
    {
        if(subtree->getRight() == nullptr )
        return NULL;
        return search(value,subtree->getRight());
    }
}

//#endif // BINARYSEARCHTREE_HPP_INCLUDED
helios (17574)
Yes, I'l like to be able to run it.
rubito (28)
Let me know if this works for you?

http://sharesend.com/i03xczv6
helios (17574)
Erm... I meant that you upload all the sources so that I can compile and run the program.
rubito (28)
They all should be in the zip file? Would you like me to add them here as code?
helios (17574)
I'd be easier if you uploaded them somewhere as a file.
rubito (28)
You can download it from here then.

http://sharesend.com/i03xczv6
helios (17574)
Okay, now I see it.
1. An empty tree starts with a root of value 0. An empty tree should have no root. m_root = nullptr.
2. This check is not right. See if you can find the problem:
if ((subtree->getLeft() == nullptr && subtree->getRight()) == nullptr)

Your print function is ignoring the root.
rubito (28)
This are the instructions:

if the current node's left and right subtree's are empty (both m_left and m_right are looking at nullptr) then return the nullptr to indicate we didn't find the value


So should I make them separate if statements?
helios (17574)
Look closely at the parentheses.
rubito (28)
Ohh, there's an extra parenthesis! Should it be:

1
2
 
 
    if (subtree->getLeft() == nullptr && subtree->getRight() == nullptr)

rubito (28)
That was totally it. Thanks a lot helios! Just one more thing? I thought that I always initialized m_root to nullptr? I don't quite understand why it would be 0 at any point?
helios (17574)
1
2
 
    m_root = new Node<T>;
    m_root->setValue(nullptr);
You're initializing m_root to a node whose value is nullptr. But since in your usage T = int, the value of the root node is zero.
root = node(NULL) is different from root = NULL.
Last edited on
rubito (28)
So, to fix this I should just initialize m_root to NULL instead of a node with value nullptr? This way m_root's value won't change during runtime?
helios (17574)
Well, nullptr is preferable, but yes.

This way m_root's value won't change during runtime?
What do you mean? The problem is that you're adding a value to the tree that the user never added.
rubito (28)
When I set 
1
2
 
m_root = new Node<T>;
m_root->setValue(nullptr);


to 
1
2
 
 
m_root = nullptr;


I get the following ouput

Input a number to put in the tree: 5
Done adding numbers? (y/n): n
Input a number to put in the tree: 4
Done adding numbers? (y/n): n
Input a number to put in the tree: 3
Done adding numbers? (y/n): n
Input a number to put in the tree: 2
Done adding numbers? (y/n): n
Input a number to put in the tree: 10
Done adding numbers? (y/n): y

Tree currently has the following values:
5 4 3 2 10
Here are sorted values:
2 3 4 10

Input a number to search for in the tree:


That is, when sorting the values, the first inputted value is missing. Is there a way to stop this from happening?
Pages: 12