Tree node with bounds

tree_node_with_bounds.cpp

/*
 * Eusebius Ngemera
 * EE2 Data Structures 2015
 */

#include <iostream>

using namespace std;

struct treeNode{
    int data;
    int lBound;
    int uBound;
    treeNode *left;
    treeNode *right;
};

typedef treeNode * tNodePtr;

int nodeCount(tNodePtr hdTree);
int nodesInRange(tNodePtr hdTree, int LB, int UB);
void insertNode(tNodePtr &hdTree, int data);
void updateBounds(tNodePtr hdTree);
void maxDensity(tNodePtr hdTree, tNodePtr &maxP, float &maxD); // max density node pointer and value
void printTree(tNodePtr hdTree);
void printNode(tNodePtr hdTree);

int main(){
    
    tNodePtr hdTree = NULL;
    tNodePtr maxDensity_ptr;
    float maxDensity_value;
    
    int input_nums[4] = {3, 0, 19, -21};
    for(int i=0; i<4; i++)
    	insertNode(hdTree, input_nums[i]);
    cout << nodeCount(hdTree) << " node(s)" << endl;
    printTree(hdTree);
    
    maxDensity(hdTree, maxDensity_ptr, maxDensity_value);
    cout << "Highest density is " << maxDensity_value << ":" << endl;
    printNode(maxDensity_ptr);

    return 0;
}

int nodeCount(tNodePtr hdTree){
    if(hdTree == NULL)
        return 0;

    return nodeCount(hdTree->left) + nodeCount(hdTree->right) + 1;
}

int nodesInRange(tNodePtr hdTree, int LB, int UB){
    if(hdTree == NULL)
        return 0;

    int currNode = 0;

    if(hdTree->lBound >= LB && hdTree->uBound >= UB)
        currNode = 1;

    return nodesInRange(hdTree->left, LB, UB) + nodesInRange(hdTree->right, LB, UB) + currNode;
}

void insertNode(tNodePtr &hdTree, int data){
    if(hdTree == NULL){
        tNodePtr temp;
        temp = new treeNode;

        temp->data = data;
        temp->lBound = data;
        temp->uBound = data;
        temp->left = NULL;
        temp->right = NULL;

        hdTree = temp;
    }
    else if(data < hdTree->data){
        if(data < hdTree->lBound)
            hdTree->lBound = data;

        insertNode(hdTree->left, data);
    }
    else{
        if(data > hdTree->uBound)
            hdTree->uBound = data;

        insertNode(hdTree->right, data);
    }
}

void updateBounds(tNodePtr hdTree){
    if(hdTree != NULL){
        tNodePtr boundP = hdTree;

        // lower bound
        while(boundP->left != NULL)
            boundP = boundP->left;

        if(boundP->data < hdTree->lBound)
            hdTree->lBound = boundP->data;

        // upper bound
        boundP = hdTree;

        while(boundP->right != NULL)
            boundP = boundP->right;

        if(boundP->data > hdTree->uBound)
            hdTree->uBound = boundP->data;

        // recurse
        updateBounds(hdTree->left);
        updateBounds(hdTree->right);
    }
}

void maxDensity(tNodePtr hdTree, tNodePtr &maxP, float &maxD){
    if(hdTree != NULL){
        float currDensity = nodeCount(hdTree)/(hdTree->uBound - hdTree->lBound + 1.0);

        if(currDensity > maxD){
            maxD = currDensity;
            maxP = hdTree;
        }

        maxDensity(hdTree->left, maxP, maxD);
        maxDensity(hdTree->right, maxP, maxD);
    }
}

// additions

void printTree(tNodePtr hdTree){
	if(hdTree != NULL){
		printTree(hdTree->left);
		printNode(hdTree);
		printTree(hdTree->right);
	}
}

void printNode(tNodePtr hdTree){
	if(hdTree != NULL){
		cout << hdTree->data << " ("<<hdTree->lBound<<","<<hdTree->uBound<<")"<< endl;
	}
}