How to search a binary tree with user input

[Mgramlin]

Hello. I am trying to search for an element in a binary search tree using a class object but I cant get my code to work right. I have a class called Stock which has three private members: compName, compSymbol, compPrice. Here I am supposed to ask the user for a Stock symbol, search for that stock in the tree, and then display the name of that stock. Every time I try to search for a Stock symbol it just outputs 'Not found' even if I know it is in there. I don't understand why I can't get it to work. I am not looking for the solution, just a push in the right direction!!

Here is what I have in main. This is the code I am having promblems with:

int main()
{
    BinarySearchTree<Stock> tree;
    Stock company[23];
    string name,
        symbol;
    const int DISPLAY_NAME = 1,        
        DISPLAY_PRICE = 2,
        INSERT = 3,
        DISPLAY_ALL = 4,
        QUIT = 5;
//this is a menu driven program, i only posted the part of the program i am having issues with
    if (choice == DISPLAY_PRICE)
        {
             //Stock tempSymbol;
            cout << "Enter the stock's symbol to display the price: ";
            cin >> symbol;


            //symbol = tempSymbol.getSymbol();


            //tempSymbol.setSymbol(symbol);
            Stock* ptr = tree.search(symbol);


            if (ptr == nullptr)
                cout << "Not found.\n";
            else
                cout << ptr->getPrice();


            cout << endl;
        }
}

I tried using Stock's member functions get and set (accessor and mutator member functions) for both the symbol and the price but I still can't get it to work. I left a little bit of what I tried in the code above and commented it out.

Here are some of the functions in the Stock class. The rest of the code here is just for clarification :

class Stock
{
private:
    string compName;
    string compSymbol;
    double compPrice;
public:
    string getName() const;
    void setName(string name);
    string getSymbol() const;
    void setSymbol(string symbol);
    double getPrice() const;
    void setPrice(double price);
}

And then the code in the BinarySearchTree is this (this is also just here for clarification):

template <typename T>
T* BinarySearchTree<T>::search(const T& item) const
{
    T* result;
    result = search(root, item);


    return result;
}


template <typename T>
T* BinarySearchTree<T>::search(Node<T>*r, const T& item) const
{
    T* result;


    if (r == nullptr)
        result = nullptr;


    else if (r->info > item)
        result = search(r->left, item);


    else if (r->info < item)
        result = search(r->right, item);


    else
        result = new T(r->info);


    return result;
}

[jonnin]

search works just like insert. typically its recursive, in pseudocode..

is this node null? If so, you didnt find it, stop.
is it *this* node? If yes, found it, return else
is it > *this node value* ... call self with right else
call self with left.

[Mgramlin]

I'm not haveing trouble with the search function itself, I'm having trouble with calling it in main(). I'm supposed to ask the user for a Stock class symbol and then search for in the binary search tree, then display the name of the Stock. But I can't get the code in my main() function to work right

[jonnin]

what exactly is it doing wrong? You seem to be calling it correctly and doing what you wanted.
search seems odd, why is it making a new, uninitialized node and returning it (and the returned item is dereferenced in main print, bad!)? I don't think search works, but I can't test it easily in fragments.

also, maybe initialize result to null just to be safe.

[TheIdeasMan]

The variable result is a local variable, so it is destroyed at the end of the function, this is an error. Why didn't your compiler complain about that? You could pass a reference to result as a parameter of the function, store the answer there.

The search function doesn't seem to have the base case, as per jonnin's psuedo:

jonnin wrote:

is it *this* node? If yes, found it, return

The other base case is item not found return nullptr

And I agree with jonnin, why create a new node in the search function?

Also, have a go at learning how to use a debugger: step through code 1 line at a time; keep an eye on the values of variables in the watchlist; deduce what went wrong. This will vastly improve your learning experience.

Finally there are zillions of examples on the internet.

[jonnin]

I think you CAN use result as a local because its value is always null or a valid pointer. Its returning a value. However, result is not even needed. you can just return the values, and that is cleaner.

that is, assuming his code is correct, which it isn't, you can take result out:

template <typename T>
T* BinarySearchTree<T>::search(Node<T>*r, const T& item) const
{
    T* result;


    if (r == nullptr)
        result = nullptr; 
return nullptr;


    else if (r->info > item)
        return(search(r->left, item));


    else if (r->info < item)
        return(search(r->right, item));


    else
        result = new T(r->info);


    return result;
  return nullptr; 
}

presumably somewhere in there you also have if this node data == search target, return this node. With that, its just eventually going to hit all returns and back propagate the answer. I don't even think the final return is needed, but leaving it there rather than what-if broken code.