Binary Search Tree

[ellimist14]

I have my BST built and it's working. But the only thing that doesn't seem to be working are the following functions which I built to print out the maximum and minimum of the gpa's (each tree node contains a struct of an ID, gpa, and age). It prints out the same thing for both and it seems neither are right.

void IntBinaryTree::displayMaxandMin(TreeNode *nodePtr)
{
	double min, max;
	min = findMin(nodePtr);
	cout << "The lowest gpa in the class is: "<< min<<endl;
	max = findMax(nodePtr);
	cout << "The highest gpa in the class is: "<< max<<endl;
}


double IntBinaryTree::findMin(TreeNode *nodePtr)
{
	
	double min = 1000.00;
	if (nodePtr)
	{
		findMin(nodePtr->left);
		cout << nodePtr->student.gpa<<endl;
		if (nodePtr->student.gpa < min)
			min = nodePtr->student.gpa;
		findMin(nodePtr->right);
	}
	return min;
}


double IntBinaryTree::findMax(TreeNode *nodePtr)
{
	double max = 0.00;
	if (nodePtr)
	{
		findMax(nodePtr->left);
		cout << nodePtr->student.gpa<<endl;
		if (nodePtr->student.gpa > max)
			max = nodePtr->student.gpa;
		findMax(nodePtr->right);
	}
	return max;
}

[Clinton Portis]

You want to return the min and max gpa from your binary search tree.

Q. Is your tree sorted by gpa? If so, (if ascending order), your lowest gpa would be on the lowest far-left node. Conversely, your high gpa would be on the lowest far-right node.

If BST is not sorted by GPA, I am not sure you can traverse the tree starting from the root node and guarantee that ->right nodes will be greater GPA's, and ->left nodes will be lesser GPA's.

If this is the case, you can provide a function that will sort your BST based on the GPA attribute. One quick and dirty method would be to push your BST into an array, sort the array based on GPA. At this point you might as well get the min and max GPA... In this scenario, you lose the speedy quickness of using a BST, but you only need 1 BST to exist in memory.

Another possibility would be to create copies of the BST that are sorted by attribute. In this case, have 3 trees.. one sorted by ID, one sorted by GPA, one sorted by age. Then just search the appropriate BST as needed to return speedy results for the given attribute.

Another possibility is to sift through every node of the BST, keeping track of min and max GPA along the way (why even use a BST if you do this.. )

There are probably better methods out there..

[Intrade]

Well you're comparing the gpa of each individual node to a seperate "min"/"max" on the stack.

Of course your output wont be correct.

Keep in mind that you're using recursion, and you want to pass the new minimum value to each method as well to determine the true minimum value.

[ellimist14]

omg of course that makes perfect sense

[Intrade]

I fiddled around with the code and came up with this.

#include <cstdlib>
#include <iostream>
#include <string>

using namespace std;

struct Student{

      double gpa;
      int id;
      int age;
      
      Student(int a = 0, int b = 0, int c = 0){
                  gpa = a;
                  id = b;
                  age = c;
      }      
};

struct TreeNode{
      
      TreeNode* left;
      TreeNode* right;
      Student student;
      
      TreeNode() : left(0), right(0){}
};

struct IntBinaryTree{
      
      TreeNode* root;
      
      void displayMaxandMin(TreeNode* nodePtr);
      double findMin(TreeNode* nodePtr, double);
      double findMax(TreeNode* nodePtr, double);
      void displayTree();

      private:
              
              void displayTreeHelper(TreeNode* node, string tab);
};

void IntBinaryTree::displayTree(){
     
     if(root){
              displayTreeHelper(root, "");
     }
}

void IntBinaryTree::displayTreeHelper(TreeNode* node, string tab){
     
     if(node == 0){
             return;    
     }else{
            
           displayTreeHelper(node->right, tab + "\t");
           cout << tab << node->student.gpa <<endl;
           displayTreeHelper(node->left, tab + "\t");
     }
}

double IntBinaryTree::findMin(TreeNode *nodePtr, double min)
{
	if (nodePtr)
	{
		if (nodePtr->student.gpa < min)
			min = nodePtr->student.gpa;
		min = findMin(nodePtr->left, min);
		min = findMin(nodePtr->right, min);
	}
    return min;
}


double IntBinaryTree::findMax(TreeNode *nodePtr, double max)
{
	if (nodePtr)
	{
		if (nodePtr->student.gpa > max)
			max = nodePtr->student.gpa;
		max = findMax(nodePtr->left, max);
		max = findMax(nodePtr->right, max);
	}
    return max;
}

void IntBinaryTree::displayMaxandMin(TreeNode* nodePtr)
{
	double min, max;
	min = findMin(nodePtr, 1000);
	cout << "The lowest gpa in the class is: "<< min<<endl;
	max = findMax(nodePtr, 0);
	cout << "The highest gpa in the class is: "<< max<<endl;
}

int main(int argc, char *argv[])
{
    IntBinaryTree ibt;
    
    TreeNode a, b, c, d, e, f, g, h, i;
    a.left = &b;
    a.right = &c;
    b.left = &d;
    b.right = &e;
    c.left = &f;
    c.right = &g;
    d.left = &h;
    d.right = &i;
    
    ibt.root = &a;
    
    a.student.gpa = 1.5;
    b.student.gpa = 3.0;
    c.student.gpa = 2.0;
    d.student.gpa = 3.6;
    e.student.gpa = 3.0;
    f.student.gpa = 2.0;
    g.student.gpa = 1.0;
    h.student.gpa = 3.0;
    i.student.gpa = 2.0;
    
    ibt.displayTree();
    ibt.displayMaxandMin(&a);
    
    system("PAUSE");
    return 0;
}