Search for secondary data in BST

Question

I have built a BST that holds a name as it's primary data, along with the weight associated with that name (as in when the info is inserted it goes in as Tom - 150, but is sorted in the tree by Tom). I need to be able to determine who has the lowest weight and I am not sure how to go about it. Below is the code for the class and the add method, I have plenty others, but don't feel the need to post them as they seem unrelated (I can if needed though).

    #include <iostream>

using namespace std;

class tNode
{
public:
string name;
int wt;
tNode *left, *right;

tNode()
{
    left = right = 0;
}

tNode(string name, int wt, tNode *l = 0, tNode *r = 0)
{
    this->name = name;
    this->wt = wt;
    left = l;
    right = r;
}
};

class bSTree
{
public:
tNode *root;

bSTree()
{
    root = 0;
}

bool add(string name, int wt)
{
    tNode *temp = root, *prev = 0;
    while (temp != 0)
    {
        prev = temp;
        if (name < temp->name)
        {
            temp = temp->left;
        }
        else
        {
            temp = temp->right;
        }
    }

    if (root == 0)
    {
        root = new tNode(name, wt);
    }
    else if (name < prev->name)
    {
        prev->left = new tNode(name, wt);
    }
    else if (name > prev->name)
    {
        prev->right = new tNode(name, wt);
    }
    else
    {
        return false;
    }
    return true;
}

Anyways, what is the technique of doing this? I found the lowest name value (alphabetically) by just going down the left of the tree as far as it could, but I am not 100% sure on the technique for finding the lowest weight, since the tree is not sorted by the weight. I'm not experienced as I'd like to be in c++ and the only thing I can think of is going through every weight, inputting the data to an int, then sorting the ints to find the lowest. I can't imagine this is the correct way to do it, or at least the most efficient. Any help is always appreciated. Thanks!

EDIT: This is what I have came up with so far:

void searchWeight(tNode* temp)
{
    // DETERMINE LOWEST WEIGHT CONTAINED IN TREE

    if (temp != 0)
    {
    cout << temp->wt << endl;
    searchWeight(temp->left);
    searchWeight(temp->right);
    }
}

This will output all of the weights to the console, but I'm not sure how to go through each one and determine the lowest. I've tried putting another if statement in there where

 if(currwt < minwt)
    minwt = currwt

but no luck with it outputting properly in the end.

Answer 1

You will need to loop through the entire BST since you're not searching by the tree's primary key. You can use any of the tree traversal algorithms.

If you need to search by weight a large number of times (and simply searching the entire tree isn't fast enough), then it will be worth it to build an "index", i.e. a second BST that points to the nodes in the first BST, but is sorted on the secondary key.

Looping through the tree once will be O(n), but looping through the tree m times will be O(m*n). Building a second binary search tree with different index will be O(n*log(n)), and then searching the second tree m times will be O(m*log(n)), so the entire operation is O(n*log(n)+m*log(n)) = O((n+m)*log(n)).

Answer 2

You do not have to sort the tree to get the node with minimum weight. Just do a traversal of the tree and store the lowest weight and the person who has the lowest weight. Update the two variables if the current node's weight is less than the minimum weight. You will have the lowest weight at the end of the traversal.

The pseudocode will look something like,

minWeight = 0
minWeightPerson = ""

for each node in the tree:
    if ( minWeight > weight of current node):
        minWeight = weight of current node
        minWeightPerson = person in current node

return minWeightPerson